整列アルゴリズムとは？バブルソート・クイックソート・マージソートなどを基礎から理解しよう

はじめに

前回は、データの中から目的の値を探す探索アルゴリズムについて学びました。

今回は、データを順番に並べ替える整列アルゴリズムについて学びます。

例えば、

[5][2][8][1][4]

というデータを、

[1][2][4][5][8]

と小さい順に並べる処理です。

このような処理を、

整列（Sort：ソート）

と呼びます。

整列アルゴリズムにはさまざまな種類があり、

バブルソート
選択ソート
挿入ソート
シェルソート
クイックソート
マージソート
ヒープソート

などがあります。

名前だけを見ると多く感じますが、

どのような考え方でデータを並べ替えているのか

を理解すると、それぞれの違いが見えてきます。

1. 整列とは

**整列（Sorting）**とは、

決められた基準に従ってデータを順番に並べ替える処理

です。

例えば、

[8][3][5][1][7]

を小さい順にすると、

[1][3][5][7][8]

となります。

小さいものから大きいものへ並べることを**昇順（Ascending Order）**と呼びます。

反対に、

[8][7][5][3][1]

のように大きいものから小さいものへ並べることを**降順（Descending Order）**と呼びます。

2. なぜ整列するの？

データを整列しておくと、その後の処理を効率化できる場合があります。

例えば前回学んだ二分探索では、

[2][5][8][12][16][23][30]

のようにデータが整列されている必要がありました。

つまり、

データを整列
↓
二分探索が利用できる
↓
効率よく探索できる

という関係があります。

そのため整列は、多くのプログラムで利用される基本的な処理です。

3. 整列アルゴリズムには種類がある

同じ、

[5][2][8][1][4]

を、

[1][2][4][5][8]

にする場合でも、その方法は一つではありません。

例えば、

隣同士を比較する

方法もあれば、

一番小さいものを探す

方法もあります。

さらに、

データを分割する

方法や、

木構造を利用する

方法もあります。

この「並べ替え方の違い」が、それぞれの整列アルゴリズムの特徴です。

4. バブルソートとは

**バブルソート（Bubble Sort）**とは、

隣り合うデータを比較し、順番が逆なら交換する

ことを繰り返す整列アルゴリズムです。

例えば、

[5][3][8][2]

を昇順に並べます。

まず、

5 と 3

を比較します。

5 > 3

なので交換します。

[3][5][8][2]

次に、

5 と 8

を比較します。

順番は正しいので交換しません。

[3][5][8][2]

次に、

8 と 2

を比較します。

交換すると、

[3][5][2][8]

となります。

5. バブルソートでは大きな値が端へ移動する

1回端まで比較すると、

[3][5][2][8]

となり、最大値の8が一番右へ移動しました。

次は、まだ整列されていない部分について同じ操作を行います。

[3][5][2] [8]

さらに比較と交換を繰り返すと、

[3][2][5][8]

さらに、

[2][3][5][8]

となり、整列が完了します。

大きな値が泡のように端へ浮かんでいくイメージから、Bubble Sortと呼ばれます。

6. バブルソートの計算量

バブルソートでは、多くの要素について隣同士の比較を繰り返します。

データ数をnとすると、平均・最悪の場合の時間計算量は、

O(n²)

です。

例えばデータ数が大きくなると、比較回数が急激に増えます。

そのため、

仕組みは非常に分かりやすいが、大量データには効率がよくない

という特徴があります。

7. 選択ソートとは

**選択ソート（Selection Sort）**とは、

未整列部分から最小値を探し、先頭のデータと交換する

ことを繰り返すアルゴリズムです。

例えば、

[5][3][8][2]

から最小値を探します。

最小値 = 2

です。

そこで先頭の5と交換します。

[2][3][8][5]

これで先頭の2が確定します。

8. 選択ソートを続ける

次は、

[3][8][5]

から最小値を探します。

最小値は、

なので、そのままです。

次に、

[8][5]

から最小値を探します。

なので8と交換します。

[2][3][5][8]

これで整列完了です。

つまり、

一番小さい値を選ぶ
↓
先頭へ置く
↓
次に小さい値を選ぶ
↓
次へ置く

という処理です。

9. 選択ソートの計算量

選択ソートでは、最小値を探すために未整列部分を順番に調べます。

そのため時間計算量は、

O(n²)

です。

バブルソートと同じオーダですが、基本的な選択ソートでは交換回数が比較的少ないという特徴があります。

10. バブルソートと選択ソートの違い

ここは区別しておきましょう。

バブルソート

隣同士を比較
↓
必要なら交換
↓
繰り返す

選択ソート

最小値を探す
↓
所定の位置と交換
↓
繰り返す

つまり、

バブル
→ 隣同士

選択
→ 最小値を選択

です。

11. 挿入ソートとは

**挿入ソート（Insertion Sort）**とは、

整列済みの部分へ、新しいデータを正しい位置に挿入していく

アルゴリズムです。

トランプを手札に並べる場面を想像すると分かりやすいです。

例えば、

[3][5][8]

という整列済みのデータへ、

を追加するとします。

4は、

3 < 4 < 5

なので、

[3][4][5][8]

へ挿入します。

12. 挿入ソートの流れ

例えば、

[5][3][8][2]

を整列します。

まず5を整列済みと考えます。

[5] [3][8][2]

3を適切な位置へ挿入します。

[3][5] [8][2]

次に8を挿入します。

[3][5][8] [2]

最後に2を適切な位置へ入れます。

[2][3][5][8]

これで完成です。

13. 挿入ソートの計算量

挿入ソートの平均・最悪時間計算量は、

O(n²)

です。

ただし、すでにほとんど整列されているデータでは、移動や比較が少なくて済みます。

そのため、

ほぼ整列済みのデータに強い

という特徴があります。

最良の場合は、

O(n)

程度で処理できます。

14. 3つの基本ソートを整理する

ここまでの3種類を整理します。

アルゴリズム	基本的な考え方	平均時間計算量
バブルソート	隣同士を比較・交換	O(n²)
選択ソート	最小値を選んで交換	O(n²)
挿入ソート	適切な位置へ挿入	O(n²)

どれも比較的理解しやすい一方、大量のデータでは効率が悪くなりやすいアルゴリズムです。

15. シェルソートとは

**シェルソート（Shell Sort）**は、挿入ソートを改良したアルゴリズムです。

挿入ソートでは、遠く離れた場所へデータを移動する場合、

1つずつ
↓
1つずつ
↓
1つずつ

と移動させる必要があります。

そこでシェルソートでは、

最初は離れた位置のデータ同士を比較し、徐々に間隔を狭める

という方法を使います。

16. シェルソートのイメージ

例えば、

[8][3][7][4][9][2][6][1]

というデータがあるとします。

最初は一定の間隔を空けて、

のようなグループを作り、それぞれを整列します。

その後、

間隔を小さくする

ことで全体を徐々に整えていきます。

最後には間隔を1にして、挿入ソートと同じように整列します。

17. シェルソートのポイント

シェルソートでは、最初に大まかに並べ替えることで、

完全にバラバラ
↓
だいたい整列
↓
挿入ソート

という状態にできます。

挿入ソートは「ほぼ整列済み」のデータに強いため、この性質を利用しています。

なお、シェルソートの計算量はどのような間隔（ギャップ）の列を使用するかによって変わります。

そのため、

シェルソート = 必ずこの計算量

と単純には決まりません。

18. クイックソートとは

**クイックソート（Quick Sort）**は、非常に代表的な高速整列アルゴリズムです。

基本的な考え方は、

基準となる値を決め、それより小さいデータと大きいデータに分割する

ことです。

この基準となる値を**ピボット（Pivot）**と呼びます。

19. クイックソートの流れ

例えば、

[6][3][8][5][2][7]

があるとします。

ここでは例として5をピボットにします。

Pivot = 5

すると、

5より小さい
[3][2]

Pivot
[5]

5より大きい
[6][8][7]

のように分けられます。

20. 分割を繰り返す

次に、

[3][2]

や、

[6][8][7]

について同じような分割を繰り返します。

最終的に、

[2][3][5][6][7][8]

となります。

つまり、

データ
↓
ピボットで分割
↓
小さいグループ / 大きいグループ
↓
さらに分割
↓
整列

という考え方です。

21. 分割統治法

クイックソートでは、

大きな問題を小さな問題に分割して解く

という考え方が使われています。

この考え方を**分割統治法（Divide and Conquer）**と呼びます。

大きな問題
↓
小さな問題へ分割
↓
それぞれを解く
↓
全体の答えを得る

というアルゴリズム設計の考え方です。

クイックソート以外のアルゴリズムでも利用されます。

22. クイックソートの計算量

クイックソートの平均時間計算量は、

O(n log n)

です。

そのため、大量のデータに対しても高速に動作することが期待できます。

しかし、常にO(n log n)ではありません。

23. クイックソートが遅くなる場合

例えば、ピボットの選び方が悪く、

1 | 2 3 4 5 6 7

さらに、

2 | 3 4 5 6 7

さらに、

3 | 4 5 6 7

のように、一方に極端に偏った分割を繰り返すとします。

すると、効率よく半分に分割できません。

このような場合、最悪時間計算量は、

O(n²)

になります。

前回の二分探索木でも、

バランスがよい
→ 効率がよい

一方向へ偏る
→ 効率が低下

という話がありました。

クイックソートでも、分割のバランスが重要です。

24. マージソートとは

**マージソート（Merge Sort）**も、分割統治法を利用する代表的な整列アルゴリズムです。

基本的には、

データを小さく分割し、整列しながら結合する

方法です。

「マージ（Merge）」には、

結合する

という意味があります。

25. マージソートの分割

例えば、

[8][3][6][2]

を考えます。

まず半分に分割します。

[8][3]   [6][2]

さらに分割します。

[8] [3] [6] [2]

1個のデータになれば、それ以上分割する必要はありません。

26. 整列しながら結合する

次に、分割したデータを整列しながら結合します。

[8] + [3]
↓
[3][8]

同じように、

[6] + [2]
↓
[2][6]

となります。

最後に、

[3][8]
+
[2][6]

を小さいものから選びながら結合すると、

[2][3][6][8]

となります。

27. マージソートの計算量

マージソートの時間計算量は、

O(n log n)

です。

クイックソートとは異なり、データの並び方によって最悪O(n²)になることはなく、

最悪でも O(n log n)

で処理できます。

一方、一般的な配列上のマージソートでは、結合処理のために追加の作業領域を必要とします。

そのため、

高速で安定した計算量を持つが、追加メモリが必要になりやすい

という特徴があります。

28. クイックソートとマージソート

両方とも分割統治法を利用しますが、考え方が異なります。

クイックソート

ピボットを決める
↓
大小に分割
↓
それぞれを整列

マージソート

半分に分割
↓
さらに分割
↓
整列しながら結合

整理すると、

クイックソート
→ 分割するときが重要

マージソート
→ 結合するときが重要

と考えると分かりやすいです。

29. ヒープソートとは

**ヒープソート（Heap Sort）**は、**ヒープ（Heap）**という木構造を利用する整列アルゴリズムです。

前回の記事で完全二分木について学びました。

ヒープは、完全二分木を基本として、親子の値に一定のルールを持たせたデータ構造です。

例えば最大ヒープでは、

親ノードの値が子ノード以上になる

ように配置します。

30. 最大ヒープ

例えば、

を見てみましょう。

となっています。

そのため、一番大きな値が必ず根にあります。

最大値
↓
  9

この性質を利用して整列するのがヒープソートです。

31. ヒープソートの流れ

ヒープソートでは、まずデータからヒープを構築します。

例えば最大ヒープなら、

最大値
↓
根

になります。

そこで、

根の最大値を取り出す
↓
残ったデータでヒープを再構成
↓
次の最大値を取り出す
↓
繰り返す

ことで順番にデータを取り出せます。

32. ヒープと配列

ヒープは完全二分木なので、配列と相性がよいデータ構造です。

例えば、

なら、

[9][7][8][2][4]

のように格納できます。

添字を0から始める場合、

左の子
2i + 1

右の子
2i + 2

で求められます。

前回の木構造の記事で学んだ知識が、ここでそのまま使えます。

33. ヒープソートの計算量

ヒープソートの時間計算量は、

O(n log n)

です。

最悪の場合でも、

O(n log n)

に収まります。

また、配列上でヒープを構成してその場で並べ替える実装では、大きな追加配列を必要としません。

そのため、

計算量
+
追加メモリ

という点でも特徴のあるアルゴリズムです。

34. 安定ソートとは

整列アルゴリズムでは、安定性という考え方があります。

例えば、

点数80：Aさん
点数70：Bさん
点数80：Cさん

というデータがあるとします。

点数で並べ替えたとき、

80：Aさん
80：Cさん
70：Bさん

のように、同じ値を持つデータ同士の元の順序が保たれる整列を**安定ソート（Stable Sort）**と呼びます。

35. 安定性が重要になる例

例えば最初に、

名前順

で整列した後、

点数順

で安定ソートするとします。

同じ点数の人については、元の名前順を維持できます。

つまり、

同じキーを持つデータの元の順番を残したい

場合に安定性が重要になります。

36. 代表的なソートの安定性

一般的な実装では、次のように整理できます。

アルゴリズム	安定性
バブルソート	安定
挿入ソート	安定
マージソート	安定に実装可能
選択ソート	通常は不安定
シェルソート	通常は不安定
クイックソート	通常は不安定
ヒープソート	不安定

ただし、実装方法によって性質が変わる場合があります。

そのため「一般的な実装では」という前提で理解しておきましょう。

37. 内部整列と外部整列

整列には、

内部整列
外部整列

という分類もあります。

**内部整列（Internal Sort）**は、

整列対象を主記憶上に保持して処理する方法

です。

一方、**外部整列（External Sort）**は、

データが主記憶に収まらない場合に、補助記憶装置なども利用して整列する方法

です。

非常に大量のデータを扱う場合には、すべてをメモリへ読み込めないことがあります。

そのような場合に外部整列が必要になります。

38. 外部整列とマージ

外部整列では、データをいくつかのまとまりに分けて整列し、それらを後から結合する方法が利用されます。

イメージとしては、

大量データ
↓
複数の小さなデータへ分割
↓
それぞれ整列
↓
保存
↓
マージ
↓
全体を整列

です。

そのため、マージソートの考え方は外部整列とも相性があります。

39. 代表的な整列アルゴリズムを比較する

ここまでの内容を整理します。

アルゴリズム	基本的な考え方	平均	最悪
バブルソート	隣同士を比較・交換	O(n²)	O(n²)
選択ソート	最小値を選択	O(n²)	O(n²)
挿入ソート	適切な位置へ挿入	O(n²)	O(n²)
シェルソート	間隔を空けて挿入ソート	ギャップ列による	ギャップ列による
クイックソート	ピボットで分割	O(n log n)	O(n²)
マージソート	分割して結合	O(n log n)	O(n log n)
ヒープソート	ヒープを利用	O(n log n)	O(n log n)

この表は、応用情報の問題を解くときにも役立ちます。

40. どのアルゴリズムが一番いいの？

単純に、

O(n log n)
だから最強

とは限りません。

例えば、

データ量
メモリ使用量
元のデータの並び方
安定性が必要か
実装の複雑さ

などによって適したアルゴリズムは変わります。

例えば、

ほぼ整列済み
→ 挿入ソートが有利な場合がある

安定したO(n log n)が必要
→ マージソート

追加メモリを抑えたい
→ ヒープソートなど

平均的に高速
→ クイックソート

というように、それぞれ特徴があります。

41. 応用情報で見分けるポイント

アルゴリズムの説明から名前を判断できるようにしましょう。

隣接するデータを比較・交換

バブルソート

最小値を選んで交換

選択ソート

整列済み部分の適切な位置へ挿入

挿入ソート

一定間隔の要素を整列し、間隔を狭める

シェルソート

ピボットを基準に大小へ分割

クイックソート

分割してから整列しながら結合

マージソート

完全二分木・ヒープを利用

ヒープソート

この特徴を押さえておけば、文章からアルゴリズムを判断しやすくなります。

42. データ構造とアルゴリズムがつながってきた

ここまで学んできた内容を振り返ってみましょう。

リスト
↓
データをつなぐ

スタック
↓
LIFO

キュー
↓
FIFO

木構造
↓
階層的にデータを管理

探索
↓
目的のデータを探す

整列
↓
データを順番に並べる

そして今回、

ヒープソート
↓
完全二分木

というつながりも出てきました。

さらに、

整列済みデータ
↓
二分探索

という関係もあります。

このように、

データ構造とアルゴリズムは別々の知識ではなく、互いにつながっている

ことが分かります。

43. まとめ

整列アルゴリズムは、

データを決められた順番に並べ替えるためのアルゴリズム

です。

基本的な整列方法として、

バブルソート
選択ソート
挿入ソート

があります。

より発展的なものとして、

シェルソート
クイックソート
マージソート
ヒープソート

があります。

この記事で覚えること

整列とはデータを決められた順番に並べ替えること
小さい順を昇順、大きい順を降順という
バブルソートは隣同士を比較・交換する
選択ソートは最小値などを選んで所定の位置へ置く
挿入ソートは整列済み部分へデータを挿入する
シェルソートは間隔を空けた挿入ソートを行う
クイックソートはピボットを基準にデータを分割する
クイックソートは平均O(n log n)、最悪O(n²)
マージソートは分割したデータを整列しながら結合する
マージソートはO(n log n)
ヒープソートはヒープを利用する
ヒープソートはO(n log n)
クイックソートやマージソートでは分割統治法が使われる
同じ値を持つデータの元の順序を維持するものを安定ソートという
内部整列は主記憶上で処理する
外部整列は補助記憶装置なども利用する
整列アルゴリズムは計算量だけでなく、メモリや安定性なども考えて選ぶ

🍯 はちみつメモ

バブルは「隣と交換」、選択は「一番小さいものを選ぶ」、挿入は「正しい場所に差し込む」。クイックは「ピボットで分ける」、マージは「分けてから合体」、ヒープは「木の力を借りる」。まずはこのイメージを持つと、たくさんあるソートを整理しやすい。