分割して並べる｜マージソートとクイックソート【基本情報技術者試験 科目B】

現行FE シラバス Ver9.2 準拠擬似言語の記述形式は2022年から変更なし最終更新 2026-08-23

整列の3本目です。バブル・選択や挿入は、並び全体を1本のくり返しで片づけるやり方でした。ここからは割って、それぞれを片づけるやり方に変わります。

大きいまま解かず、割ってから解く

4つをいっぺんに並べるのは面倒です。でも半分に割れば2つずつ。もう一度割れば1つずつになります。そして1つなら、もう並んでいます。

1つになるまで割れば、並べる作業は消える

「同じやり方でまた解く」ので、手続が自分自身を呼びます。これが再帰です。ここでは「自分を呼ぶ行がある」とだけ分かれば足ります。

マージソート【手順1】1つになるまで、半分に割る

まずひたすら半分に割ります。中身は見ません。ただ真ん中で切るだけです。

1つになるまで割れば、並べる作業は消える

{5, 3, 8, 1} なら、{5, 3} と {8, 1}。もう一度割って {5} {3} {8} {1}。1つになったら、それはもう並んでいます。ここまでは何も並べ替えていません。

マージソート【手順2】並べながら、戻していく

ここからが本番です。2本ずつ、並べながらくっつけて戻します。

割るのは簡単。むずかしいのは戻すとき

やり方は1つだけ。2本の先頭どうしを比べて、小さいほうを取る。取ったほうだけ1つ進める。これをくり返します。

{1, 3, 5, 8} のできあがりです。比べた回数は4回だけ。両方すでに並んでいるので、先頭以外を見る必要がありません。

併合を、プログラムで書く

いま手で追った最後の併合を、そのままプログラムにします。a と b が併合する2本、out が結果です。

整数型の配列: a ← {3, 5}
整数型の配列: b ← {1, 8}
整数型の配列: out ← {}
整数型: p ← 1
整数型: q ← 1

while (p ≦ aの要素数 and q ≦ bの要素数)
  if (a[p] ≦ b[q])
    outの末尾 に a[p]の値 を追加する
    p ← p ＋ 1
  else
    outの末尾 に b[q]の値 を追加する
    q ← q ＋ 1
  endif
endwhile
while (p ≦ aの要素数)
  outの末尾 に a[p]の値 を追加する
  p ← p ＋ 1
endwhile
while (q ≦ bの要素数)
  outの末尾 に b[q]の値 を追加する
  q ← q ＋ 1
endwhile

当サイトで作った例です。

実行すると out は {1, 3, 5, 8} になります。p と q がそれぞれの「いま見ている位置」です。while が3つあるのは、片方が尽きたら比べる相手がいなくなるから。2つ目と3つ目が、残ったほうをそのまま写すところです。

p と q が別々に動くところは、止まった絵では追えません。動画で1周ずつ見てください。

クイックソート ── 基準値で振り分ける

こちらは順序が逆です。割る前に振り分けます。

割る前に振り分ける。だから戻すときは何もしない

②が終わった時点で、基準値の位置は決まっています。左には小さいものしかなく、右には大きいものしかないからです。だから戻すときに併合は要りません。

2つのちがい

試験では「途中経過を答えよ」という形で問われます。どちらなのかは、割ったあとに併合の行があるかどうかで見分けられます。

つまずきポイントまとめ

次に読む