こんにちは、フルスタックエンジニアのryuです。
今回の記事では、基本情報技術者試験の過去問を使いながら、クイックソートの仕組みについて解説します。
クイックソートは、データを並べ替える「整列アルゴリズム」の一つです。名前だけを見ると難しそうですが、基本的な考え方はそれほど複雑ではありません。
基準となる値を一つ決めて、それより小さい値と大きい値に分ける。
まずはこの動きを理解することが大切です。
基本情報技術者試験の科目Bでは、アルゴリズムの名前を暗記するだけではなく、擬似言語を読みながら処理の流れを追う力が必要になります。
この記事では、過去問の選択肢を確認しながら、クイックソートの動き、他のソートとの違い、擬似言語を読むときのポイントまで順番に解説します。
クイックソートの処理方法を説明したものはどれか¶
今回はこちらの問題です。
クイックソートの処理方法を説明したものはどれか。
ア：既に整列済みのデータ列の正しい位置に、データを追加する操作を繰り返していく方法である。 イ：データ中の最小値を求め、次にそれを除いた部分の中から最小値を求める。この操作を繰り返していく方法である。 ウ：適当な基準値を選び、それより小さな値のグループと大きな値のグループにデータを分割する。同様にして、グループの中で基準値を選び、それぞれのグループを分割する。この操作を繰り返していく方法である。 エ：隣り合ったデータの比較と入替えを繰り返すことによって、小さな値のデータを次第に端のほうに移していく方法である。
答えは、ウです。
クイックソートでは、基準値を一つ選び、その値を基準にデータを小さいグループと大きいグループへ分けます。
この「基準値を決めて分割する」という部分が、クイックソートを見分ける大きなポイントです。
クイックソートとは？¶
クイックソートとは、データを分割しながら並べ替えていくアルゴリズムです。
クイックソートでは、まずデータの中から基準となる値を一つ選びます。この基準値を「ピボット」と呼ぶことがあります。
例えば、次のデータを小さい順に並べ替えてみましょう。
8 3 7 4 9 2 6
今回は、分かりやすく最初の8を基準値にしてみます。
基準値：8
8より小さい値と、大きい値に分けます。
8より小さい
3 7 4 2 6
基準値
8
8より大きい
9
これで、少なくとも8より小さい値は左側、8より大きい値は右側に分けられました。
次は、左側のグループでも同じことを行います。
3 7 4 2 6
例えば3を基準値にすると、
3より小さい
2
基準値
3
3より大きい
7 4 6
となります。
さらに、
7 4 6
でも同じように基準値を決めて分割していきます。
この操作を繰り返すことで、最終的にデータ全体が整列されます。
クイックソートは「分ける」を繰り返す¶
クイックソートを理解するときは、細かいコードから覚えるよりも、まず次の流れを覚えると分かりやすいです。
- 基準値を一つ決める
- 基準値より小さい値を片方に集める
- 基準値より大きい値を反対側に集める
- 分けたグループでも同じ処理を行う
- グループをこれ以上分ける必要がなくなるまで繰り返す
つまり、
基準値を決める
↓
小さい値 ｜ 基準値 ｜ 大きい値
↓
それぞれでも同じ処理
というアルゴリズムです。
基本情報技術者試験でクイックソートの説明を選ぶ問題が出た場合は、「基準値」「分割」という言葉に注目すると判断しやすくなります。
他の選択肢は何のアルゴリズム？¶
今回の問題は、クイックソートだけを覚えていても解けます。
ただ、他の選択肢が何を表しているのかまで理解しておくと、整列アルゴリズム全体の整理になります。
アは挿入ソート¶
アは、
既に整列済みのデータ列の正しい位置に、データを追加する操作を繰り返していく
という説明です。
これは挿入ソートです。
例えば、
3 7
まで整列されていて、次に5を追加するとします。
5は3より大きく、7より小さいので、
3 5 7
という位置に挿入します。
このように、整列済みの部分へ新しい値を正しい位置に入れていくのが挿入ソートです。
イは選択ソート¶
イは、
データ中の最小値を求め、次にそれを除いた部分の中から最小値を求める
という説明です。
これは選択ソートです。
例えば、
5 3 8 1
があれば、まず一番小さい1を探します。
1 3 8 5
次に、残った部分から一番小さい値を探します。
「まだ並んでいない部分から最小値を選ぶ」と考えると覚えやすいです。
エはバブルソート¶
エは、
隣り合ったデータの比較と入替えを繰り返す
という説明です。
これはバブルソートです。
例えば、
5 3 8 1
で、隣同士を比較して順番が逆なら入れ替えます。
5 3
↓
3 5
この比較と入替えを繰り返して、値を少しずつ端へ移動させます。
今回の4つを整理すると、次のようになります。
| アルゴリズム | 見分けるポイント |
|---|---|
| 挿入ソート | 整列済みの部分へ正しい位置に挿入する |
| 選択ソート | 最小値などを選んで順番に確定する |
| クイックソート | 基準値を使って小さい・大きいグループに分割する |
| バブルソート | 隣り合う値を比較して入れ替える |
名前だけではなく、「どんな動きをするのか」とセットで覚えるのがおすすめです。
クイックソートを擬似言語で考えてみよう¶
現在の基本情報技術者試験の科目Bでは、アルゴリズムを擬似言語で読む力が必要になります。
そのため、「クイックソート＝基準値で分ける」と覚えるだけではなく、処理がコードになったときにも追えるようにしておきたいです。
説明用に簡単な形で表すと、次のような流れになります。
quickSort(data)
if (dataの要素数が1以下)
dataを返す
endif
pivot ← dataの中から一つ選ぶ
small ← pivotより小さい値
large ← pivotより大きい値
small ← quickSort(small)
large ← quickSort(large)
small、pivot、largeをつなげて返す
ここで注目したいのが、
quickSort(small)
quickSort(large)
です。
クイックソートの中から、もう一度クイックソートを呼び出しています。
このように、処理の中から自分自身を呼び出すことを再帰と呼びます。
科目Bでは再帰処理も理解しておきたい内容なので、クイックソートを学ぶときに一緒に覚えておくとよいでしょう。
再帰が分からなくても、まずは分割を追えばいい¶
「自分自身を呼び出す」と聞くと、一気に難しく感じるかもしれません。
最初から再帰を完璧に理解しようとしなくても大丈夫です。
例えば、
8 3 7 4 9 2 6
をクイックソートするときは、まず、
3 7 4 2 6 ｜ 8 ｜ 9
に分かれます。
そのあと左側の、
3 7 4 2 6
だけに注目します。
それをさらに、
2 ｜ 3 ｜ 7 4 6
のように分けます。
つまり再帰処理も、最初は、
「分けたグループに対して、もう一度同じ作業をしている」
と考えると分かりやすいです。
コードだけを見て理解しようとするより、実際の数字を並べて分割してみるのがおすすめです。
科目Bでクイックソートが出たら何を追えばいい？¶
クイックソートが擬似言語で出題された場合、すべての変数を頭の中だけで追うと途中で分からなくなりやすいです。
まずは次の3つを確認してください。
- どの値が基準値になっているか
- 現在どの範囲を処理しているか
- 基準値より小さい側と大きい側がどう変化したか
例えば、
pivot ← data[1]
と書かれていれば、「最初の要素を基準値にしている」と考えます。
また、
if (data[i] < pivot)
のような条件があれば、「基準値より小さい値を探している」と分かります。
いきなり1行目から最後まで読むのではなく、基準値と比較している部分を先に見つけると、処理の目的が見えやすくなります。
クイックソートは本当に速いの？¶
クイックソートは、その名前のとおり高速に動作しやすい整列アルゴリズムです。
平均的な計算量は、
O(n log n)
です。
ただし、「クイックソートなら必ず速い」という意味ではありません。
基準値の選び方やデータの並び方によっては、分割が偏ってしまうことがあります。
例えば、毎回、
1個 ｜ 残り全部
のような分かれ方をしてしまうと、効率が悪くなります。
最悪の場合の計算量は、
O(n²)
です。
基本情報技術者試験では、アルゴリズム名だけではなく、このような計算量の違いが問われることもあります。
初心者のうちは、
- 平均的には
O(n log n) - 分割が偏ると遅くなることがある
くらいから覚えておけばよいと思います。
擬似言語は「答えを覚える」だけでは解けるようにならない¶
基本情報技術者試験の勉強をしていると、過去問の答えを覚えてしまうことがあります。
今回の問題も、
「クイックソートはウ」
と覚えるだけなら簡単です。
ただ、科目Bではそれだけでは足りません。
実際には擬似言語を読み、
「この変数は何を表しているのか」 「このif文では何を比較しているのか」 「この繰返しで配列がどう変化するのか」
を追う必要があります。
そのため、アルゴリズムを勉強するときは、答えだけではなく実際のデータを使って動きを確認することが大切です。
クイックソートなら、自分で適当な数字を並べて、
- 基準値を決める
- 小さい値と大きい値に分ける
- 分けたグループでも同じことをする
という流れを一度やってみてください。
かなり理解しやすくなります。
Giji Academyで整列アルゴリズムを実践的に学ぶ¶
科目Bのアルゴリズム対策で難しいのは、解説を読んで理解したつもりでも、実際に擬似言語になると読めなくなることです。
私も、アルゴリズムはコードを眺めているだけより、実際に値を変えたり処理を追ったりした方が理解しやすいと思っています。
Giji Academyでは、基本情報技術者試験の科目Bで使う擬似言語を、ブラウザ上で実行しながら学習できます。
変数、条件分岐、繰返し、配列、トレースなどの基礎から始めて、探索・整列アルゴリズムまで段階的に学べます。
「クイックソートの説明は分かったけど、擬似言語になると読めない」という場合は、いきなり難しいアルゴリズム問題を解き続けるのではなく、配列や繰返しまで戻って処理を追う練習をするのがおすすめです。
登録不要で無料体験できます。
Pythonでクイックソートを書いてみる¶
基本情報技術者試験の科目B対策では擬似言語を中心に学ぶのがおすすめですが、プログラミングそのものも勉強している方は、Pythonで実装してみても理解が深まります。
例えば、簡単な実装なら次のように書けます。
def quick_sort(arr):
if len(arr) <= 1:
return arr
pivot = arr[0]
left = []
right = []
pivot_count = 0
for value in arr:
if value < pivot:
left.append(value)
elif value > pivot:
right.append(value)
else:
pivot_count += 1
return quick_sort(left) + [pivot] * pivot_count + quick_sort(right)
次の配列を並べ替えてみます。
arr = [8, 10, 9, 1, 34, 4, 3, 7, 5, 1]
result = quick_sort(arr)
print(result)
実行結果は次のようになります。
[1, 1, 3, 4, 5, 7, 8, 9, 10, 34]
このコードでも、
pivot
left
right
に注目すると、先ほど説明した「基準値を決めて、小さい値と大きい値に分ける」という動きになっていることが分かります。
ただし、科目B対策だけが目的であれば、Pythonの文法まで新しく覚える必要はありません。
まずは擬似言語でアルゴリズムの流れを追えるようになることを優先してください。
アルゴリズムをさらに勉強したい場合¶
クイックソートを理解できたら、他の整列アルゴリズムと比較してみると理解が深まります。
今回の過去問には、
- 挿入ソート
- 選択ソート
- クイックソート
- バブルソート
が一度に登場しています。
それぞれについて、コードを丸暗記する必要はありません。
「何を比較するのか」「どのように並べ替えるのか」という特徴を説明できる状態を目指しましょう。
元記事では、アルゴリズム学習用として次の書籍も紹介していました。
![うかる！ 基本情報技術者 [午後・アルゴリズム編] 2021年版 福嶋先生の集中ゼミ (日本経済新聞出版)](https://m.media-amazon.com/images/I/51CLANtoLqL._SL500_.jpg)
こちらは旧試験制度の2021年版です。現在の科目B対策用としてそのまま使うのではなく、アルゴリズムの考え方を補助的に理解する用途で利用してください。
また、元記事で紹介していた過去問題集も旧制度向けです。画像・リンクは残していますが、現在受験する場合は科目A・科目Bに対応した最新教材を利用することをおすすめします。
まとめ¶
今回は、基本情報技術者試験の過去問を使ってクイックソートについて解説しました。
問題の答えは、
ウ：基準値を選び、それより小さい値と大きい値のグループに分割する方法
です。
クイックソートで覚えておきたいポイントは、次のとおりです。
- 基準値（ピボット）を一つ選ぶ
- 基準値より小さい値と大きい値に分ける
- 分けたグループでも同じ処理を繰り返す
- 再帰処理が使われることがある
- 平均的な計算量は
O(n log n)
科目Bでは、アルゴリズムの名前を覚えるだけではなく、「このコードが何をしているのか」を追えることが大切です。
クイックソートを理解したら、挿入ソート、選択ソート、バブルソートなどと比較しながら、それぞれの処理の違いを確認してみてください。
Giji Academyでは、擬似言語の基礎から配列、繰返し、トレース、探索・整列アルゴリズムまで、ブラウザ上で実際にコードを動かしながら学習できます。
「科目Bの解説を読めば分かるけど、自分では擬似言語を追えない」という方は、まず基礎から実際に動かしてみてください。
Giji Academy｜擬似言語を実行しながら科目Bを学ぶ
あわせて読みたい
