【初心者向け】定番ソートアルゴリズム徹底解説：PHP/Pythonサンプルコード付き

By /

【初心者向け】定番ソートアルゴリズム徹底解説：PHP/Pythonサンプルコード付き

ソート（整列）アルゴリズムは、プログラミングの基礎であり、データ構造を理解する上で非常に重要な概念です。この記事では、ソートアルゴリズムの基礎知識から、代表的なアルゴリズムであるバブルソート、選択ソート、挿入ソート、マージソート、クイックソートについて、図解、PHPとPythonのサンプルコード、それぞれのアルゴリズムのメリット・デメリット、計算量（時間複雑度・空間複雑度）まで詳しく解説します。プログラミング初心者の方でも理解しやすいように、丁寧に説明することを心がけました。

1. ソートアルゴリズムとは？なぜ学ぶ必要があるのか

ソートアルゴリズムとは、データの集合（配列やリストなど）を、特定の順序（昇順や降順など）に並び替えるためのアルゴリズムのことです。例えば、数字の配列[5, 2, 8, 1, 9]を昇順にソートすると[1, 2, 5, 8, 9]になります。

ソートアルゴリズムを学ぶ必要がある理由は、主に以下の3点です。

  • 効率的なデータ処理: ソートされたデータは、検索や分析が非常に容易になります。例えば、電話帳は名前順にソートされているため、目的の人の名前を素早く見つけることができます。データベースのインデックスも、ソートされたデータを高速に検索するために利用されます。
  • アルゴリズム思考の基礎: ソートアルゴリズムは、問題を解決するための基本的な考え方（分割統治、再帰など）を学ぶための良い題材となります。これらの考え方は、他の複雑なアルゴリズムを理解する上でも役立ちます。
  • プログラミングスキルの向上: ソートアルゴリズムを実装することで、配列やリストの操作、条件分岐、ループ処理といった基本的なプログラミングスキルを向上させることができます。また、異なるアルゴリズムを比較検討することで、効率的なコードを書くための理解を深めることができます。

2. ソートアルゴリズムの分類

ソートアルゴリズムは、様々な基準で分類することができます。代表的な分類方法としては、以下のものがあります。

  • 比較ソート vs. 非比較ソート:
    • 比較ソート: 要素同士を比較して順序を決定するアルゴリズムです。バブルソート、選択ソート、挿入ソート、マージソート、クイックソートなどが該当します。
    • 非比較ソート: 要素の値を直接参照して順序を決定するアルゴリズムです。計数ソート、基数ソートなどが該当します。
  • 内部ソート vs. 外部ソート:
    • 内部ソート: データをすべてメモリ上に展開してソートするアルゴリズムです。この記事で解説するアルゴリズムはすべて内部ソートです。
    • 外部ソート: データが大きすぎてメモリに収まらない場合に、外部記憶装置（ハードディスクなど）を利用してソートするアルゴリズムです。
  • 安定ソート vs. 不安定ソート:
    • 安定ソート: 同じ値を持つ要素の順序が、ソート後も変わらないアルゴリズムです。
    • 不安定ソート: 同じ値を持つ要素の順序が、ソート後に変わる可能性があるアルゴリズムです。

3. 基本的なソートアルゴリズム

ここでは、代表的なソートアルゴリズムであるバブルソート、選択ソート、挿入ソートについて、図解、PHPとPythonのサンプルコード、メリット・デメリット、計算量を詳しく解説します。

3.1. バブルソート（Bubble Sort）

バブルソートは、隣り合う要素を比較し、順序が逆であれば交換する操作を繰り返すことで、配列をソートするアルゴリズムです。まるで泡（バブル）が水面に向かって上がっていくように、大きい要素が配列の末尾に移動していくことから、バブルソートと呼ばれます。

図解:

例えば、配列[5, 1, 4, 2, 8]をバブルソートで昇順にソートする過程を見てみましょう。

  1. 1回目のループ:

    • (5, 1)を比較: 5 > 1 なので交換 -> [1, 5, 4, 2, 8]
    • (5, 4)を比較: 5 > 4 なので交換 -> [1, 4, 5, 2, 8]
    • (5, 2)を比較: 5 > 2 なので交換 -> [1, 4, 2, 5, 8]
    • (5, 8)を比較: 5 < 8 なので交換しない -> [1, 4, 2, 5, 8]
    • 1回目のループ終了後: [1, 4, 2, 5, 8] (最大の要素である8が末尾に移動)

  2. 2回目のループ:

    • (1, 4)を比較: 1 < 4 なので交換しない -> [1, 4, 2, 5, 8]
    • (4, 2)を比較: 4 > 2 なので交換 -> [1, 2, 4, 5, 8]
    • (4, 5)を比較: 4 < 5 なので交換しない -> [1, 2, 4, 5, 8]
    • 2回目のループ終了後: [1, 2, 4, 5, 8]

  3. 3回目のループ:

    • (1, 2)を比較: 1 < 2 なので交換しない -> [1, 2, 4, 5, 8]
    • (2, 4)を比較: 2 < 4 なので交換しない -> [1, 2, 4, 5, 8]
    • 3回目のループ終了後: [1, 2, 4, 5, 8]

  4. 4回目のループ:

    • (1, 2)を比較: 1 < 2 なので交換しない -> [1, 2, 4, 5, 8]
    • 4回目のループ終了後: [1, 2, 4, 5, 8]

このように、ループを繰り返すことで、最終的に配列がソートされます。

PHPサンプルコード:

“`php

$array[$j + 1]) {
// 交換
$temp = $array[$j];
$array[$j] = $array[$j + 1];
$array[$j + 1] = $temp;
}
}
}
return $array;
}

$array = [5, 1, 4, 2, 8];
$sortedArray = bubbleSort($array);
print_r($sortedArray); // 出力: Array ( [0] => 1 [1] => 2 [2] => 4 [3] => 5 [4] => 8 )

?>

“`

Pythonサンプルコード:

“`python
def bubble_sort(array):
n = len(array)
for i in range(n – 1):
for j in range(n – i – 1):
if array[j] > array[j + 1]:
# 交換
array[j], array[j + 1] = array[j + 1], array[j]
return array

array = [5, 1, 4, 2, 8]
sorted_array = bubble_sort(array)
print(sorted_array) # 出力: [1, 2, 4, 5, 8]
“`

メリット:

  • 実装が簡単で理解しやすい。

デメリット:

  • 効率が悪く、大きなデータセットには不向き。
  • 平均計算量、最悪計算量ともにO(n^2)。

計算量:

  • 時間計算量:
    • 最良: O(n) (すでにソート済みのデータ)
    • 平均: O(n^2)
    • 最悪: O(n^2)
  • 空間計算量: O(1) (定数)

3.2. 選択ソート（Selection Sort）

選択ソートは、未ソートの部分から最小（または最大）の要素を見つけ、それを未ソートの部分の先頭（または末尾）に移動させる操作を繰り返すことで、配列をソートするアルゴリズムです。

図解:

例えば、配列[6, 4, 1, 5, 3]を選択ソートで昇順にソートする過程を見てみましょう。

  1. 1回目のループ:

    • 未ソート部分: [6, 4, 1, 5, 3]
    • 最小値: 1 (インデックス 2)
    • 1と6を交換 -> [1, 4, 6, 5, 3]

  2. 2回目のループ:

    • 未ソート部分: [4, 6, 5, 3]
    • 最小値: 3 (インデックス 3)
    • 3と4を交換 -> [1, 3, 6, 5, 4]

  3. 3回目のループ:

    • 未ソート部分: [6, 5, 4]
    • 最小値: 4 (インデックス 2)
    • 4と6を交換 -> [1, 3, 4, 5, 6]

  4. 4回目のループ:

    • 未ソート部分: [5, 6]
    • 最小値: 5 (インデックス 0)
    • 5と5を交換 -> [1, 3, 4, 5, 6]

このように、ループを繰り返すことで、最終的に配列がソートされます。

PHPサンプルコード:

“`php

1 [1] => 3 [2] => 4 [3] => 5 [4] => 6 )

?>

“`

Pythonサンプルコード:

“`python
def selection_sort(array):
n = len(array)
for i in range(n – 1):
min_index = i
for j in range(i + 1, n):
if array[j] < array[min_index]:
min_index = j
# 交換
array[i], array[min_index] = array[min_index], array[i]
return array

array = [6, 4, 1, 5, 3]
sorted_array = selection_sort(array)
print(sorted_array) # 出力: [1, 3, 4, 5, 6]
“`

メリット:

  • 実装が簡単で理解しやすい。
  • バブルソートよりも交換回数が少ない。

デメリット:

  • 効率が悪く、大きなデータセットには不向き。
  • 平均計算量、最悪計算量ともにO(n^2)。

計算量:

  • 時間計算量:
    • 最良: O(n^2)
    • 平均: O(n^2)
    • 最悪: O(n^2)
  • 空間計算量: O(1) (定数)

3.3. 挿入ソート（Insertion Sort）

挿入ソートは、未ソートの部分から要素を1つずつ取り出し、それをソート済みの部分の適切な位置に挿入する操作を繰り返すことで、配列をソートするアルゴリズムです。トランプの手札を並び替えるイメージで考えると理解しやすいでしょう。

図解:

例えば、配列[5, 2, 4, 6, 1, 3]を挿入ソートで昇順にソートする過程を見てみましょう。

  1. 1回目のループ:

    • ソート済み部分: [5]
    • 未ソート部分: [2, 4, 6, 1, 3]
    • 2をソート済み部分の適切な位置に挿入 -> [2, 5, 4, 6, 1, 3]

  2. 2回目のループ:

    • ソート済み部分: [2, 5]
    • 未ソート部分: [4, 6, 1, 3]
    • 4をソート済み部分の適切な位置に挿入 -> [2, 4, 5, 6, 1, 3]

  3. 3回目のループ:

    • ソート済み部分: [2, 4, 5]
    • 未ソート部分: [6, 1, 3]
    • 6をソート済み部分の適切な位置に挿入 -> [2, 4, 5, 6, 1, 3]

  4. 4回目のループ:

    • ソート済み部分: [2, 4, 5, 6]
    • 未ソート部分: [1, 3]
    • 1をソート済み部分の適切な位置に挿入 -> [1, 2, 4, 5, 6, 3]

  5. 5回目のループ:

    • ソート済み部分: [1, 2, 4, 5, 6]
    • 未ソート部分: [3]
    • 3をソート済み部分の適切な位置に挿入 -> [1, 2, 3, 4, 5, 6]

このように、ループを繰り返すことで、最終的に配列がソートされます。

PHPサンプルコード:

“`php

= 0 && $array[$j] > $key) {
$array[$j + 1] = $array[$j];
$j = $j – 1;
}
$array[$j + 1] = $key;
}
return $array;
}

$array = [5, 2, 4, 6, 1, 3];
$sortedArray = insertionSort($array);
print_r($sortedArray); // 出力: Array ( [0] => 1 [1] => 2 [2] => 3 [3] => 4 [4] => 5 [5] => 6 )

?>

“`

Pythonサンプルコード:

“`python
def insertion_sort(array):
n = len(array)
for i in range(1, n):
key = array[i]
j = i – 1
while j >= 0 and array[j] > key:
array[j + 1] = array[j]
j -= 1
array[j + 1] = key
return array

array = [5, 2, 4, 6, 1, 3]
sorted_array = insertion_sort(array)
print(sorted_array) # 出力: [1, 2, 3, 4, 5, 6]
“`

メリット:

  • 実装が簡単で理解しやすい。
  • すでにソート済みのデータや、ほぼソート済みのデータに対しては高速に動作する。
  • 安定ソートである。

デメリット:

  • 効率が悪く、大きなデータセットには不向き。
  • 平均計算量、最悪計算量ともにO(n^2)。

計算量:

  • 時間計算量:
    • 最良: O(n) (すでにソート済みのデータ)
    • 平均: O(n^2)
    • 最悪: O(n^2)
  • 空間計算量: O(1) (定数)

4. 高度なソートアルゴリズム

ここでは、より効率的なソートアルゴリズムであるマージソートとクイックソートについて、図解、PHPとPythonのサンプルコード、メリット・デメリット、計算量を詳しく解説します。

4.1. マージソート（Merge Sort）

マージソートは、分割統治法と呼ばれるアルゴリズム設計技法を用いたソートアルゴリズムです。配列を再帰的に半分に分割し、分割された各部分をソートした後、それらをマージ（結合）することで、ソートされた配列を得ます。

図解:

例えば、配列[8, 3, 1, 7, 0, 10, 2]をマージソートで昇順にソートする過程を見てみましょう。

  1. 分割:

    • [8, 3, 1, 7, 0, 10, 2] -> [8, 3, 1, 7] と [0, 10, 2]
    • [8, 3, 1, 7] -> [8, 3] と [1, 7]
    • [0, 10, 2] -> [0, 10] と [2]
    • [8, 3] -> [8] と [3]
    • [1, 7] -> [1] と [7]
    • [0, 10] -> [0] と [10]
    • 各要素が1つになるまで分割

  2. マージ:

    • [8] と [3] をマージ -> [3, 8]
    • [1] と [7] をマージ -> [1, 7]
    • [0] と [10] をマージ -> [0, 10]
    • [3, 8] と [1, 7] をマージ -> [1, 3, 7, 8]
    • [0, 10] と [2] をマージ -> [0, 2, 10]
    • [1, 3, 7, 8] と [0, 2, 10] をマージ -> [0, 1, 2, 3, 7, 8, 10]

このように、分割とマージを繰り返すことで、最終的に配列がソートされます。

PHPサンプルコード:

“`php

0 [1] => 1 [2] => 2 [3] => 3 [4] => 7 [5] => 8 [6] => 10 )

?>

“`

Pythonサンプルコード:

“`python
def merge_sort(array):
if len(array) <= 1:
return array

mid = len(array) // 2
left = array[:mid]
right = array[mid:]

left = merge_sort(left)
right = merge_sort(right)

return merge(left, right)

def merge(left, right):
result = []
i = 0
j = 0

while i < len(left) and j < len(right):
if left[i] <= right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1

result += left[i:]
result += right[j:]
return result

array = [8, 3, 1, 7, 0, 10, 2]
sorted_array = merge_sort(array)
print(sorted_array) # 出力: [0, 1, 2, 3, 7, 8, 10]
“`

メリット:

  • 安定ソートである。
  • 時間計算量が常にO(n log n)であるため、安定した性能を発揮する。

デメリット:

  • 再帰処理を使用するため、メモリ消費量が多い。
  • 内部ソートであるため、大規模なデータセットには不向きな場合がある。

計算量:

  • 時間計算量:
    • 最良: O(n log n)
    • 平均: O(n log n)
    • 最悪: O(n log n)
  • 空間計算量: O(n)

4.2. クイックソート（Quick Sort）

クイックソートも、分割統治法と呼ばれるアルゴリズム設計技法を用いたソートアルゴリズムです。配列からピボットと呼ばれる要素を1つ選び、そのピボットを基準にして配列を2つの部分に分割します。分割された各部分に対して再帰的にクイックソートを適用することで、ソートされた配列を得ます。

図解:

例えば、配列[7, 2, 1, 6, 8, 5, 3, 4]をクイックソートで昇順にソートする過程を見てみましょう。

  1. ピボットの選択:

    • 最初の要素である7をピボットとして選択

  2. 分割:

    • 7より小さい要素: [2, 1, 6, 5, 3, 4]
    • 7より大きい要素: [8]

  3. 再帰的なソート:

    • [2, 1, 6, 5, 3, 4] に対してクイックソートを適用
    • [8] は要素が1つなのでソート済み

  4. 結合:

    • ソートされた [2, 1, 6, 5, 3, 4] の結果 + ピボット 7 + ソートされた [8] の結果

このように、ピボットの選択、分割、再帰的なソート、結合を繰り返すことで、最終的に配列がソートされます。

PHPサンプルコード:

“`php

1 [1] => 2 [2] => 3 [3] => 4 [4] => 5 [5] => 6 [6] => 7 [7] => 8 )

?>

“`

Pythonサンプルコード:

“`python
def quick_sort(array):
if len(array) <= 1:
return array

pivot = array[0]
left = [x for x in array[1:] if x <= pivot]
right = [x for x in array[1:] if x > pivot]

left = quick_sort(left)
right = quick_sort(right)

return left + [pivot] + right

array = [7, 2, 1, 6, 8, 5, 3, 4]
sorted_array = quick_sort(array)
print(sorted_array) # 出力: [1, 2, 3, 4, 5, 6, 7, 8]
“`

メリット:

  • 平均計算量がO(n log n)であり、高速にソートできる。
  • 内部ソートであるため、メモリ効率が良い。

デメリット:

  • ピボットの選択方法によっては、最悪計算量がO(n^2)になる場合がある。
  • 安定ソートではない。

計算量:

  • 時間計算量:
    • 最良: O(n log n)
    • 平均: O(n log n)
    • 最悪: O(n^2)
  • 空間計算量: O(log n) (再帰の深さに依存)

5. まとめ

この記事では、代表的なソートアルゴリズムであるバブルソート、選択ソート、挿入ソート、マージソート、クイックソートについて、図解、PHPとPythonのサンプルコード、メリット・デメリット、計算量を詳しく解説しました。

各アルゴリズムの特徴を理解し、データセットの規模や特性に応じて適切なアルゴリズムを選択することが重要です。

アルゴリズム 時間計算量 (最良) 時間計算量 (平均) 時間計算量 (最悪) 空間計算量 安定ソート メリット デメリット
バブルソート O(n) O(n^2) O(n^2) O(1) ○ 実装が簡単で理解しやすい 効率が悪く、大きなデータセットには不向き
選択ソート O(n^2) O(n^2) O(n^2) O(1) × 実装が簡単で理解しやすい、交換回数が少ない 効率が悪く、大きなデータセットには不向き
挿入ソート O(n) O(n^2) O(n^2) O(1) ○ 実装が簡単で理解しやすい、ソート済みデータに強い 効率が悪く、大きなデータセットには不向き
マージソート O(n log n) O(n log n) O(n log n) O(n) ○ 安定ソート、時間計算量が安定している メモリ消費量が多い
クイックソート O(n log n) O(n log n) O(n^2) O(log n) × 平均計算量が高速、メモリ効率が良い ピボット選択によっては最悪計算量がO(n^2)になる

ソートアルゴリズムは、プログラミングの基礎として非常に重要な概念です。この記事を参考に、ぜひ様々なソートアルゴリズムを実装し、理解を深めてください。そして、より効率的なプログラムを作成するために、適切なアルゴリズムを選択できるようになりましょう。

コメントする

メールアドレスが公開されることはありません。 ※ が付いている欄は必須項目です

上部へスクロール