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

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

期間限定クーポンPR｜Udemy の講座科目B オリジナル模試 3回分・60問42%OFF 1,500円~~2,600円~~中身を見る ›

この回の内容を動画で見る

講義の実際の画面公開記念・いまだけ先着100名0円~~通常 2,600円~~有料講座「科目B 基礎講義」プログラムを1行ずつたどり、値がどう変わるかを動画で見せます。この回の講義もこの講座に入っています。講義の目次と無料の1本を見るUdemy・12月3日まで・100名に達したら通常価格に戻ります

次のページで講義の目次と無料の講義を見られます。受講ボタンとクーポンコードもそこにあります。

大きいまま解かず、割ってから解く
マージソート【手順1】1つになるまで、半分に割る
マージソート【手順2】並べながら、戻していく
併合を、プログラムで書く
クイックソート ── 基準値で振り分ける
2つのちがい
つまずきポイントまとめ
次に読む

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

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

分割統治

大きい問題を小さい問題に割って、同じやり方でまた解く。これを分割統治といいます。シラバスにも用語として載っています。

割っただけでは、並びません

割るのはただ半分にするだけで、何も考えていません。並べる仕事は消えたのではなく、戻すときに回されています。次に見るのは、その戻し方です。

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

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

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

{5, 3, 8, 1} を、1つになるまで半分に割る

枡の上の数字＝要素番号　／　色の付いた枡＝そのかたまりの中は、もう並んでいる

はじめ（4つ）

まん中で割る（2つずつ）

もう一度割る（1つずつ）

1つなら、もう並んでいる。ここまで、どの値も元の位置から動いていない。

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

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

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

2本ずつ、並べながら戻す

枡の上の数字＝要素番号　／　色の付いた枡＝そのかたまりの中は、もう並んでいる

1つずつ

2本ずつ併合する（2つずつに戻る）

5 と 3 では、小さい 3 が先。8 と 1 では、小さい 1 が先。

もう一度併合する（4つに戻る）

{3, 5} と {1, 8} の先頭どうしを比べ、小さいほうから取る。1 → 3 → 5、残った 8。

割るときは何も並べていない。並べているのは、この戻り道。

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

最後の併合を、手で追う

{3, 5} と {1, 8}先頭は 3 と 1。小さい 1 を取る

{3, 5} と {8}先頭は 3 と 8。小さい 3 を取る

{5} と {8}先頭は 5 と 8。小さい 5 を取る

{} と {8}片方が空。残った 8 はそのまま追加する

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

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

いま手で追った最後の併合を、そのままプログラムにします。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つ目が、残ったほうをそのまま追加するところです。

併合を1行ずつ動かす

当サイトオリジナルの例題

ループ開始前

並んでいる2本と、併合先

▲ いま読んでいる▲ いま書いた

いま計算していること

まだ計算していません

変数の状態

トレース表（進めると1行ずつ積み上がります）

番号（添字）が2つ要るのは、どういうときか

2本の要素数が同じで、同じ番号が同じものを指すなら、番号は1つで足ります（A2-1）。

ここのように 2本を先頭から見比べて、取り出した側だけを進めるなら、2つ要ります。毎周どちらか片方しか進みません。

マージソートの重さは、戻すところにある

割るのはただ半分にするだけで、何も考えません。仕事はすべて併合のときに起きます。

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

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

{5, 1, 3, 2, 4} を、基準値 3 で振り分けてから並べる

枡の上の数字＝要素番号　／　枠だけ色の付いた枡＝基準値　／　色の付いた枡＝位置が決まった

① 基準値を1つ決める

まん中の 3 を基準値にする。

② 3 より小さいものは左、大きいものは右へ寄せる

左にあった 5 と、右にあった 2 が入れ替わる。3 の位置は、ここで決まる。左と右の中は、まだ並んでいない。

③ 左と右を、それぞれ同じやり方で並べる

戻すときは何もしない。全体がもう並んでいる。

やること

①基準値（pivot）を1つ決める

②それより小さいものを左、大きいものを右へ寄せる

③左と右を、それぞれ同じやり方で並べる

②が終わった時点で、左には基準値以下のものしかなく、右には基準値以上のものしかありません。この例では基準値 3 の位置もここで決まります。だから戻すときに併合は要りません。

実際の出題にそのまま出ている

令和5年度の科目Bに、大域の配列 data の、first 番目から last 番目までを昇順に整列する sort という手続が出ています。

基準値の決め方は pivot ← data[(first ＋ last) ÷ 2 の商]。まん中の要素を選んでいます。÷ 2 の商 は、2で割った整数の商という意味です（A2-1）。

最後に sort(first, i － 1) と sort(j ＋ 1, last) ── 自分を2回呼んでいます。基準値の左のかたまりと、右のかたまりです。i と j は、振り分けが終わったときの左右の境目の番号で、上の図の例ならどちらも 3。sort(1, 2) と sort(4, 5) になります。

2つのちがい

	マージソート	クイックソート
割り方	まん中で機械的に半分	基準値で振り分けてから割る
仕事の場所	戻すとき（併合）	割る前（振り分け）
戻すとき	2本を突き合わせて併合	何もしない。すでに並んでいる

令和5年度問3 は、振り分けが1回終わった時点の並びを答える出題でした。どちらなのかは、割ったあとに併合の行があるかどうかで見分けられます。

つまずきポイントまとめ

まちがえ方	正しい読み方
クイックソートでも併合すると思う	振り分け済みなので併合は要らない
マージソートで割るときに何か考える	割るのは機械的に半分。仕事は戻すとき
`÷ 2 の商` を小数のまま計算する	`の商` が付いたら整数。`5 ÷ 2 の商` は 2
自分を呼ぶ行を見落とす	手続の中に、同じ名前の呼び出しがある
振り分けたあとで左右をまたいで動くと思う	左のかたまりと右のかたまりは、もう混ざらない

次に読む

A7-1	2分探索 ─ まん中と比べて、探す範囲を半分にする
第2部	科目Bのアルゴリズム ─ 出るものの地図
A5-2	挿入ソート ─ 手札を並べるのと同じ
目次	基本情報技術者試験科目B 攻略ガイド