科目Bのクイックソート問題の解き方｜基準値で分ける手順を追う

ピボットで分けるところまでは読めた。でも、再帰に入った瞬間に迷子になる。

科目Bでクイックソートのコードを見て、どこから追えばいいのか分からなくなったことはありませんか？

交換の処理が何度も起き、そのうえ関数が自分自身を呼び出します。配列の中身と呼び出しの範囲を同時に覚えておこうとして、頭がいっぱいになってしまう人も多いのではないでしょうか。

大丈夫です。クイックソートの問題の多くは、1回の分割で配列がどうなるかを追えれば解けるように作られています。

私はエンジニアとして10年以上、Webシステムの開発や運用に携わってきました。並べ替えそのものは言語の標準機能に任せることがほとんどですが、データを条件で2つのグループに分けて、それぞれに同じ処理をかける書き方は、集計やバッチ処理で何度も使ってきました。

一度、グループ分けの境目にある1件だけが、どちらの処理にも入らずに抜け落ちる不具合を出したことがあります。原因は範囲の端の指定で、境目の値を含む小さなデータを手で追って、ようやく気づけました。

この記事では、クイックソートの問題を、科目Bの解き方に合わせて5つの段階で紹介します。科目B全体の中で、こうしたアルゴリズムの問題がどんな位置にあるのかを先に確かめたい人は、親記事から読んでおくと流れがつかみやすくなります。

【関連記事】基本情報技術者試験の科目Bとは？擬似言語・アルゴリズム対策を初心者向けに解説

クイックソートの問題は何を聞いているのか¶

最初に、クイックソートが何をする並べ替えなのかを短く押さえておきましょう。クイックソートとは、基準になる値を1つ選び、それより小さい値と大きい値に配列を分ける操作を、分けた範囲ごとに繰り返す並べ替えのことです。

この基準になる値を、ピボットと呼びます。ピボットより小さい値を左に、大きい値を右に集めると、ピボット自身は並べ替え後の正しい位置に収まります。

あとは、左の範囲と右の範囲に同じ操作をかければよいだけです。同じ操作を小さな範囲にかけ直すので、コードでは再帰呼び出しの形になります。

ほかの並べ替えとの違いを表で比べる¶

科目Bには、クイックソート以外にもいくつかの並べ替えが出てきます。それぞれ何を繰り返しているのかを表に並べると、違いが見えやすくなります。

表のとおり、クイックソートは平均すると速い並べ替えです。ただし、ピボットの選び方が悪く、毎回片側にしか値が残らない場合は、O(n²) まで遅くなります。

隣どうしを入れ替える交換ソートの追い方は、こちらの記事で詳しく扱っています。比べながら読むと、クイックソートの交換が離れた位置どうしで起きていることがよく分かります。

【関連記事】科目Bのソート問題を解くコツ｜交換される値を追ってみよう

まず目を付ける場所¶

クイックソートの考え方がつかめたら、次はコードのどこから読むかを決めます。この問題で目を付ける場所は3つです。

ひとつ目はピボットをどこから取っているか、ふたつ目は小さい値の集まりの境目を表す変数、みっつ目は再帰呼び出しに渡している範囲です。この3か所を確かめれば、残りの行はほとんど交換の手続きにすぎません。

ピボットはどこから取っているか¶

最初に確かめたいのが、ピボットを配列のどの位置から取っているかです。先頭、末尾、真ん中のどれを選ぶかで、分割の結果が変わるからです。

科目Bでは、範囲の末尾の値をピボットにする書き方がよく見られます。ただし真ん中を選ぶ問題もあるので、思い込まずに代入の行を必ず読んでください。

境目を表す変数は何か¶

次に見るのが、ピボットより小さい値がどこまで集まったかを覚えている変数です。この記事の例題では i がその役目を持っています。

i は、小さい値の集まりの右端を指しています。小さい値が1つ見つかるたびに i を1つ進め、その位置に見つけた値を交換で運び込みます。

再帰に渡す範囲はどうなっているか¶

最後に見るのが、分割のあとで自分自身を呼び出す行です。ピボットの左側と右側を、それぞれどこからどこまでとして渡しているかを確かめます。

ここで大切なのは、ピボットの位置そのものを再帰の範囲に含めていないことです。範囲の端が1つずれるだけで、いつまでも同じ範囲を呼び続けるコードになってしまいます。

例題：末尾の値をピボットにして配列を分ける¶

ここからは、実際の例題で追い方を確かめます。この記事の例題は説明のために作成したもので、IPA の公開問題そのものではありません。

次のプログラムは、大域変数の配列 data の first 番目から last 番目までを、昇順に並べ替える手続です。配列の要素番号は1から始まるものとします。

大域: 整数型の配列: data ← {5, 3, 8, 1, 9, 2, 6}

○quicksort(整数型: first, 整数型: last)
  整数型: pivot, i, j, tmp
  if (first ≧ last)
    return
  endif
  pivot ← data[last]
  i ← first － 1
  for (j を first から last － 1 まで 1 ずつ増やす)
    if (data[j] ＜ pivot)
      i ← i ＋ 1
      tmp ← data[i]
      data[i] ← data[j]
      data[j] ← tmp
    endif
  endfor
  tmp ← data[i ＋ 1]
  data[i ＋ 1] ← data[last]
  data[last] ← tmp
  quicksort(first, i)
  quicksort(i ＋ 2, last)

for の部分が分割です。末尾の値をピボットにして、それより小さい値を左へ集めていきます。

for が終わったら、ピボットを小さい値の集まりのすぐ右、つまり i ＋ 1 番目に移します。そのあと、ピボットの左右をそれぞれ再帰で並べ替えます。

では、quicksort(1, 7) を呼び出したとき、最初の再帰呼び出しの直前で data はどうなっているでしょうか？

トレース表で分割の1回目を追う¶

再帰まで一度に追おうとすると、配列の中身と範囲が頭の中で混ざってしまいます。そこで、まずは最初の分割だけに絞り、for の1回ごとに j、data[j]、比較の結果、i、交換後の配列をトレース表に書きます。

ピボットは data[7] の 6 で、i は 0 から始まります。

1行目と2行目では、i と j が同じ位置なので、自分自身との交換になり配列は変わりません。4行目で初めて、3番目の 8 と4番目の 1 が入れ替わります。

for が終わった時点で i は 4 です。最後に5番目の 9 と7番目のピボット 6 を入れ替えるので、data は 5, 3, 1, 2, 6, 8, 9 になります。

これが問いの答えです。ピボットの 6 は5番目に収まり、左には6より小さい値、右には6より大きい値だけが並んでいます。

トレース表の書き方そのものに慣れていない場合は、こちらの記事で基本から確認できます。

【関連記事】擬似言語のトレース表の書き方｜科目Bで変数の値を追う手順を解説

再帰の呼び出しは範囲だけを表に書く¶

分割が終わったら、次は quicksort(1, 4) と quicksort(6, 7) が呼ばれます。ここからは配列の中身をすべて書くのではなく、呼び出しの範囲と、その範囲のピボットだけを表にすると迷いません。

(1, 1) や (3, 2) のように、first が last 以上になった呼び出しは、最初の if ですぐに戻ります。範囲に値が1つ以下しかなければ、並べ替える必要がないからです。

すべての呼び出しが終わると、data は 1, 2, 3, 5, 6, 8, 9 になります。呼び出しの順番そのものに不安がある場合は、再帰の追い方をまとめた記事も役に立ちます。

【関連記事】基本情報科目Bの再帰呼び出しがわからない人への対策方法を解説｜擬似言語で処理を追うコツ

間違いやすい選択肢の見分け方¶

クイックソートの問題では、分割の途中の状態や、範囲の端を少しだけずらした選択肢が並びます。どんな誤りが用意されやすいのかを知っておけば、選択肢を見た瞬間に候補を絞れます。

例題の最初の分割を使って、よくある誤りを表にまとめました。

2行目は特に引っかかりやすい選択肢です。問いが最初の再帰呼び出しの直前を聞いているなら、左右の中身はまだ並んでいないはずだと考えてください。

1回の分割で保証されるのは、ピボットの位置と、左右に小さい値と大きい値が分かれていることだけです。左右それぞれの中の順番は、まだばらばらのままです。

空欄の穴埋めは境目の条件で確かめる¶

穴埋めの問題では、比較の行が空欄になっていることがよくあります。＜ か ≦ か、pivot と比べるのか data[last] と比べるのかが選択肢になります。

迷ったときは、分割が終わった直後の配列で、ピボットの左に6以上の値が混ざっていないかを確かめてください。混ざっていたら、比較の向きか対象が違っています。

再帰の範囲は端の値で試す¶

再帰の範囲が空欄になっているときは、ピボットがいちばん大きい値だった場合を考えるのが近道です。たとえば data が 2, 1, 9 で末尾の 9 がピボットなら、for が終わった時点で i は 2 になります。

このとき quicksort(first, i ＋ 1) という選択肢を選ぶと、quicksort(1, 3) がもう一度呼ばれます。範囲が縮まないので、同じ呼び出しが永遠に続いてしまいます。

正しい quicksort(first, i) なら、範囲は (1, 2) に縮みます。ピボットの位置を範囲から外しているかどうかが、見分けの決め手です。

平均と最悪の計算量も問われる¶

クイックソートでは、計算量を問う設問が組み合わされることもあります。すでに昇順に並んだ配列で末尾をピボットにすると、毎回片側に1つも値が残らず、分割が n 回近く続くからです。

ループの形から計算量を見積もる練習をしておくと、こうした設問にも落ち着いて答えられます。

【関連記事】擬似言語の計算量（オーダー）とは？ループの回数から処理の速さを見積もる考え方を解説

Giji Academy のシミュレーターで動かす¶

紙のトレース表で動きをつかんだら、最後は実際に動かして確かめましょう。再帰と交換が重なる処理ほど、動かして見る効果は大きくなります。

Giji Academy の擬似言語シミュレーターでは、擬似言語のコードを1行ずつ実行し、変数や配列の値が変わる様子を目で確かめられます。自分で書いたトレース表と見比べながら進めると、どの交換で予想とずれたのかがすぐに分かります。

試すときは、まず正しい quicksort を動かして、最初の分割が終わった瞬間の data を確かめてください。そのあと最後の交換の3行を消して、ピボットが末尾に残る様子を見ると、あの3行の役目が体で分かります。

慣れてきたら、ピボットを先頭の値に変えて、分け方がどう変わるかを試してみましょう。すでに並んでいる配列を渡して、呼び出しの回数が増える様子を見ておくのもおすすめです。

まずはGiji Academy の擬似言語シミュレーターで講座を選び、ピボットを境に値が左右へ分かれていく流れを確かめてみてください。

まとめ¶

科目Bのクイックソートの問題は、再帰の全体を一度に追うことを求めているわけではありません。1回の分割でピボットがどこに収まり、左右に何が分かれるのかを表に書いて追えば、落ち着いて解けます。

この記事でお伝えした5つの段階を振り返っておきましょう。

最初は、5つから7つくらいの短い配列で十分です。何度か表を書くうちに、ピボットを見ただけで、どの値が左に集まるのかが分かるようになります。

まずは1回目の分割だけを追う。再帰は範囲だけを表に書く。 この2つを習慣にしておけば、クイックソートの問題にも自信を持って向き合えます。次にピボットという言葉を見かけたら、まずは末尾の値に丸を付けてから読み始めてみてください。