【図解】ソートアルゴリズムとは？主要な種類と計算量

By /

【図解】ソートアルゴリズムとは？主要な種類と計算量の詳細な説明

はじめに：なぜソートは重要なのか？

コンピュータサイエンスの世界では、データを「並べ替える」という操作は非常に基本的かつ重要です。この「並べ替え」、すなわち「ソート（Sort）」を行うためのアルゴリズムは、様々な場面で利用されています。例えば、データベースの検索結果を特定の順序で表示したり、ファイルシステムでファイルを名前や日付で整列させたり、あるいはさらに複雑なアルゴリズム（例えば探索アルゴリズムやデータ圧縮など）の前処理としてソートが必要になることもあります。

適切にソートされたデータは、検索や処理が圧倒的に高速になります。例えば、電話帳から特定の名前を探すとき、名前がアルファベット順に並んでいなければ、最初から最後まで全てを確認しなければなりませんが、並んでいれば「あ」行は最初の数ページ、「か」行は次の数ページ、というように絞り込むことができます。これは、コンピュータがデータを扱う上でも全く同じです。

ソートアルゴリズムは数多く存在し、それぞれに得意な状況や性能が異なります。この記事では、主要なソートアルゴリズムについて、その原理、動作を図解（テキストによる配列の状態変化で表現）し、計算量（性能）、長所・短所、そして安定性といった観点から詳しく解説します。約5000語にわたり、ソートアルゴリズムの世界を深く掘り下げていきましょう。

ソートアルゴリズムを評価する基準

様々なソートアルゴリズムを理解し、比較するためには、いくつかの評価基準を知っておく必要があります。

  1. 時間計算量 (Time Complexity):

    • アルゴリズムの実行にかかる時間が、入力データのサイズ（要素数 n）に対してどの程度増大するかを示す指標です。主に「O記法（Big O Notation）」という数学的な記法を用いて表されます。例えば O(n^2) は、要素数が2倍になると実行時間が約4倍になることを意味し、O(n log n) は要素数が2倍になると実行時間が約2倍強になることを意味します。
    • 一般的に、最良ケース（Best Case）、平均ケース（Average Case）、最悪ケース（Worst Case）の3つのシナリオで評価されます。多くの場合、平均ケースと最悪ケースの性能が重視されます。
    • 計算量が小さいほど高速なアルゴリズムと言えます。O(n) < O(n log n) < O(n^2) の順で高速です（nが大きい場合）。

  2. 空間計算量 (Space Complexity):

    • アルゴリズムの実行に必要となる追加のメモリ量を示す指標です。これもO記法で表されます。O(1) は入力サイズに関わらず一定量のメモリしか使わないことを意味し、O(n) は入力サイズに比例したメモリを使用することを意味します。
    • 追加のメモリをほとんど使わないアルゴリズムは「in-place（インプレース）」ソートと呼ばれ、O(1) または O(log n) の空間計算量を持つことが多いです。

  3. 安定性 (Stability):

    • ソート対象のデータに、同じ値を持つ要素が複数含まれている場合、それらの要素のソート前の相対的な順序がソート後も維持されるかどうかを示す特性です。
    • 例：[(値: 5, 識別子: A), (値: 2, 識別子: B), (値: 5, 識別子: C)] をソートするとします。安定なソートの場合、結果は [(値: 2, 識別子: B), (値: 5, 識別子: A), (値: 5, 識別子: C)] のように、元々 A が C より前にあった順序が保たれます。不安定なソートの場合、結果が [(値: 2, 識別子: B), (値: 5, 識別子: C), (値: 5, 識別子: A)] となる可能性もあります。

  4. 内部ソート vs. 外部ソート:

    • ソート対象のデータが全てメインメモリに収まる場合を「内部ソート」と呼びます。
    • データがメインメモリに収まりきらず、ハードディスクなどの外部記憶装置を使う必要がある場合を「外部ソート」と呼びます。ほとんどの基本的なソートアルゴリズムは内部ソートを前提としています。大規模なデータに対する外部ソートでは、マージソートがよく利用されます。

これらの基準を念頭に置きながら、各アルゴリズムを見ていきましょう。

基本的なソートアルゴリズム (O(n^2)系)

これらのアルゴリズムは、原理が比較的単純で理解しやすいため、計算機科学の初学者にとって入門としてよく用いられます。しかし、要素数が多くなるにつれて性能が著しく低下するため、実用上、大規模なデータに対して直接用いられることは少ないです。計算量は平均的に O(n^2) となります。

1. バブルソート (Bubble Sort)

  • 原理: 配列の隣り合う要素を繰り返し比較し、順序が逆であれば交換することで、小さい（または大きい）要素を配列の先頭（または末尾）に移動させていくアルゴリズムです。例えるなら、水中で泡が浮き上がるように、大きな要素が徐々に末尾へ移動していく様子に似ているため「バブル（泡）ソート」と呼ばれます。

  • 動作 (図解):

    • 対象配列: [5, 2, 4, 6, 1, 3] (要素数 n=6)
    • 1回目のパス: 配列全体を走査し、隣り合う要素を比較交換します。
      • [5, 2, 4, 6, 1, 3] -> [2, 5, 4, 6, 1, 3] (5と2を交換)
      • [2, 5, 4, 6, 1, 3] -> [2, 4, 5, 6, 1, 3] (5と4を交換)
      • [2, 4, 5, 6, 1, 3] -> [2, 4, 5, 6, 1, 3] (5と6は順序通り)
      • [2, 4, 5, 6, 1, 3] -> [2, 4, 5, 1, 6, 3] (6と1を交換)
      • [2, 4, 5, 1, 6, 3] -> [2, 4, 5, 1, 3, 6] (6と3を交換)
      • 1回目のパス終了後、最大の要素 6 が末尾に確定します。対象は残りの n-1 要素となります。配列の状態: [2, 4, 5, 1, 3, 6]
    • 2回目のパス: 残り5要素 [2, 4, 5, 1, 3] に対して同様の操作を行います。
      • [2, 4, 5, 1, 3] -> … -> [2, 4, 1, 3, 5] (5が末尾に確定)
      • 配列の状態: [2, 4, 1, 3, 5, 6]
    • 3回目のパス: 残り4要素 [2, 4, 1, 3] に対して同様の操作を行います。
      • [2, 4, 1, 3] -> … -> [2, 1, 3, 4] (4が末尾に確定)
      • 配列の状態: [2, 1, 3, 4, 5, 6]
    • 4回目のパス: 残り3要素 [2, 1, 3] に対して同様の操作を行います。
      • [2, 1, 3] -> … -> [1, 2, 3] (3が末尾に確定)
      • 配列の状態: [1, 2, 3, 4, 5, 6]
    • 5回目のパス: 残り2要素 [1, 2] に対して同様の操作を行います。
      • [1, 2] -> [1, 2] (順序通り、交換なし)
      • 配列の状態: [1, 2, 3, 4, 5, 6]
    • 配列全体がソートされました。交換が発生しなかったパスがあれば、その時点でソート完了と判定する最適化も可能です。

  • コード例 (概念):
    function bubbleSort(array):
    n = length of array
    for i from 0 to n-2:
    swapped = false
    for j from 0 to n-2-i: // i回パスした後、最後のi要素は確定している
    if array[j] > array[j+1]:
    swap(array[j], array[j+1])
    swapped = true
    if not swapped: // 1回も交換がなければソート完了
    break
    return array

  • 計算量:
    • 時間計算量:
      • 最良ケース (既にソート済み): O(n) (最適化版の場合。交換が発生しないことを検知して早期終了)
      • 平均ケース: O(n^2)
      • 最悪ケース (逆順にソート): O(n^2)
    • 空間計算量: O(1) (追加のメモリは一時的な変数のみ)
  • 安定性: 安定
  • 長所: アルゴリズムが非常に単純で理解・実装しやすい。in-placeソートである。
  • 短所: 計算量が常にO(n^2)であるため、大規模なデータには不向き。非効率的。

2. 選択ソート (Selection Sort)

  • 原理: 未ソート部分の先頭から順に、未ソート部分の中から最小（または最大）の要素を探し出し、その要素と未ソート部分の先頭要素を交換していくアルゴリズムです。

  • 動作 (図解):

    • 対象配列: [5, 2, 4, 6, 1, 3] (要素数 n=6)
    • 1回目のパス:
      • 未ソート部分: [5, 2, 4, 6, 1, 3]
      • 未ソート部分の先頭: 5 (インデックス0)
      • 未ソート部分全体から最小値を探す -> 最小値は 1 (インデックス4)
      • 先頭の 5 と最小値の 1 を交換します。
      • 配列の状態: [1, 2, 4, 6, 5, 3]
      • 最初の要素 1 が確定しました。
    • 2回目のパス:
      • 未ソート部分: [2, 4, 6, 5, 3] (インデックス1から5)
      • 未ソート部分の先頭: 2 (インデックス1)
      • 未ソート部分全体から最小値を探す -> 最小値は 2 (インデックス1)
      • 先頭の 2 と最小値の 2 を交換します（同じ位置なので見かけ上は交換なし）。
      • 配列の状態: [1, 2, 4, 6, 5, 3]
      • 2番目の要素 2 が確定しました。
    • 3回目のパス:
      • 未ソート部分: [4, 6, 5, 3] (インデックス2から5)
      • 未ソート部分の先頭: 4 (インデックス2)
      • 未ソート部分全体から最小値を探す -> 最小値は 3 (インデックス5)
      • 先頭の 4 と最小値の 3 を交換します。
      • 配列の状態: [1, 2, 3, 6, 5, 4]
      • 3番目の要素 3 が確定しました。
    • 4回目のパス:
      • 未ソート部分: [6, 5, 4] (インデックス3から5)
      • 未ソート部分の先頭: 6 (インデックス3)
      • 未ソート部分全体から最小値を探す -> 最小値は 4 (インデックス5)
      • 先頭の 6 と最小値の 4 を交換します。
      • 配列の状態: [1, 2, 3, 4, 5, 6]
      • 4番目の要素 4 が確定しました。
    • 5回目のパス:
      • 未ソート部分: [5, 6] (インデックス4から5)
      • 未ソート部分の先頭: 5 (インデックス4)
      • 未ソート部分全体から最小値を探す -> 最小値は 5 (インデックス4)
      • 交換なし。
      • 配列の状態: [1, 2, 3, 4, 5, 6]
      • 5番目の要素 5 が確定しました。最後の要素 6 も自動的に確定します。
    • 配列全体がソートされました。

  • コード例 (概念):
    function selectionSort(array):
    n = length of array
    for i from 0 to n-2: // n-1個の要素を確定させれば残りの1つも確定
    minIndex = i
    for j from i+1 to n-1: // 未ソート部分から最小値を探す
    if array[j] < array[minIndex]:
    minIndex = j
    // 未ソート部分の先頭と最小値を交換
    if minIndex != i:
    swap(array[i], array[minIndex])
    return array

  • 計算量:
    • 時間計算量:
      • 最良ケース: O(n^2)
      • 平均ケース: O(n^2)
      • 最悪ケース: O(n^2) (要素の比較回数は入力順序によらず一定)
    • 空間計算量: O(1)
  • 安定性: 不安定 (交換によって同値要素の相対順序が変わる可能性がある)
  • 長所: 実装が単純。交換回数が非常に少ない（最大で n-1 回）。in-placeソートである。
  • 短所: 計算量が常にO(n^2)であるため、大規模なデータには不向き。

3. 挿入ソート (Insertion Sort)

  • 原理: 配列を「ソート済みの部分」と「未ソートの部分」に分けます。未ソート部分の先頭要素を一つ取り出し、それをソート済みの部分の適切な位置に挿入していくことで、ソート済み部分を拡大していきます。トランプの手札を整理する際、新しいカードを既に並べたカードの適切な位置に挿入していく操作に似ています。

  • 動作 (図解):

    • 対象配列: [5, 2, 4, 6, 1, 3] (要素数 n=6)
    • 最初の要素 5 はソート済みとみなします。ソート済み部分: [5] | 未ソート部分: [2, 4, 6, 1, 3]
    • ステップ 1: 未ソート部分の先頭 2 を取り出します。
      • ソート済み部分 [5] のどこに 2 を挿入するか考えます。2 < 5 なので、5 の前に挿入します。
      • ソート済み部分: [2, 5] | 未ソート部分: [4, 6, 1, 3]
      • 配列の状態: [2, 5, 4, 6, 1, 3]
    • ステップ 2: 未ソート部分の先頭 4 を取り出します。
      • ソート済み部分 [2, 5] のどこに 4 を挿入するか考えます。4 > 2、4 < 5 なので、2 と 5 の間に挿入します。
      • ソート済み部分: [2, 4, 5] | 未ソート部分: [6, 1, 3]
      • 配列の状態: [2, 4, 5, 6, 1, 3]
    • ステップ 3: 未ソート部分の先頭 6 を取り出します。
      • ソート済み部分 [2, 4, 5] のどこに 6 を挿入するか考えます。6 > 5 なので、5 の後に挿入します。
      • ソート済み部分: [2, 4, 5, 6] | 未ソート部分: [1, 3]
      • 配列の状態: [2, 4, 5, 6, 1, 3]
    • ステップ 4: 未ソート部分の先頭 1 を取り出します。
      • ソート済み部分 [2, 4, 5, 6] のどこに 1 を挿入するか考えます。1 は全ての要素より小さいので、先頭に挿入します。要素を一つずつ後ろにずらして挿入位置を確保します。
      • ソート済み部分: [1, 2, 4, 5, 6] | 未ソート部分: [3]
      • 配列の状態: [1, 2, 4, 5, 6, 3]
    • ステップ 5: 未ソート部分の先頭 3 を取り出します。
      • ソート済み部分 [1, 2, 4, 5, 6] のどこに 3 を挿入するか考えます。3 > 2、3 < 4 なので、2 と 4 の間に挿入します。要素を一つずつ後ろにずらして挿入位置を確保します。
      • ソート済み部分: [1, 2, 3, 4, 5, 6] | 未ソート部分: []
      • 配列の状態: [1, 2, 3, 4, 5, 6]
    • 未ソート部分がなくなったので、配列全体がソートされました。

  • コード例 (概念):
    function insertionSort(array):
    n = length of array
    for i from 1 to n-1: // iは未ソート部分の先頭インデックス
    key = array[i] // 未ソート部分の先頭要素
    j = i - 1 // ソート済み部分の末尾インデックス
    // keyをソート済み部分 array[0...j] に挿入する位置を探す
    while j >= 0 and array[j] > key:
    array[j+1] = array[j] // 要素を後ろにずらす
    j = j - 1
    array[j+1] = key // 適切な位置にkeyを挿入
    return array

  • 計算量:
    • 時間計算量:
      • 最良ケース (既にソート済み): O(n) (各要素をソート済み部分と比較する際に、すぐに適切な位置が見つかるため)
      • 平均ケース: O(n^2)
      • 最悪ケース (逆順にソート): O(n^2) (各要素をソート済み部分の全ての要素と比較する必要があるため)
    • 空間計算量: O(1)
  • 安定性: 安定
  • 長所: 実装が比較的単純。データ量が少ない場合や、ほぼソート済みのデータに対して非常に高速 (最良ケース O(n))。in-placeソートである。安定ソートである。
  • 短所: 要素の移動（後ろへのずらし）にコストがかかる。最悪ケース・平均ケースでO(n^2)となり、大規模なデータには不向き。

高速なソートアルゴリズム (O(n log n)系)

これらのアルゴリズムは、要素数 n が大きくなっても性能の劣化が比較的小さく、実用的なソートアルゴリズムとして広く利用されています。計算量は平均的に O(n log n) となります。log n は、おおよそ「nを2で割り続けたら何回で1になるか」を示す値です。n=1024ならlog nは約10、n=100万ならlog nは約20となり、n^2と比較してlog nは非常に小さいことが分かります。

4. マージソート (Merge Sort)

  • 原理: 配列を繰り返し半分に分割し、最終的に要素が一つだけの（ソート済みとみなせる）サブ配列にします。その後、分割したサブ配列をソートされた状態を保ちながら結合（マージ）していくことで、全体の配列をソートします。これは「分割統治法（Divide and Conquer）」と呼ばれるプログラミングパラダイムの一例です。

  • 動作 (図解):

    • 対象配列: [5, 2, 4, 6, 1, 3] (要素数 n=6)
    • 分割 (Divide):
      • [5, 2, 4, 6, 1, 3] を半分に分割 -> [5, 2, 4] と [6, 1, 3]
      • [5, 2, 4] を半分に分割 -> [5] と [2, 4]
      • [6, 1, 3] を半分に分割 -> [6] と [1, 3]
      • [2, 4] を半分に分割 -> [2] と [4]
      • [1, 3] を半分に分割 -> [1] と [3]
      • 最終的に要素が一つだけのサブ配列になります: [5], [2], [4], [6], [1], [3]
    • 統治・結合 (Conquer/Merge): 要素が一つだけのサブ配列はソート済みとみなします。これらを隣り合うもの同士、ソートしながら結合していきます。
      • [5] と [2] をマージ -> [2, 5]
      • [4] と [6] をマージ -> [4, 6]
      • [1] と [3] をマージ -> [1, 3]
      • この時点のサブ配列: [2, 5], [4, 6], [1, 3]
      • [2, 5] と [4, 6] をマージします。両方の先頭要素を比較し、小さい方を新しい配列に追加、追加した方から次の要素を取り出して比較…を繰り返します。
        • [2, 5] と [4, 6]
        • 2 < 4 -> 結果: [2] 残り: [5] と [4, 6]
        • 5 > 4 -> 結果: [2, 4] 残り: [5] と [6]
        • 5 < 6 -> 結果: [2, 4, 5] 残り: [] と [6]
        • 残った要素 6 を追加 -> 結果: [2, 4, 5, 6]
      • [2, 5] と [4, 6] のマージ結果: [2, 4, 5, 6]
      • [1, 3] はそのまま
      • この時点のサブ配列: [2, 4, 5, 6], [1, 3]
      • [2, 4, 5, 6] と [1, 3] をマージします。
        • [2, 4, 5, 6] と [1, 3]
        • 2 > 1 -> 結果: [1] 残り: [2, 4, 5, 6] と [3]
        • 2 < 3 -> 結果: [1, 2] 残り: [4, 5, 6] と [3]
        • 4 > 3 -> 結果: [1, 2, 3] 残り: [4, 5, 6] と []
        • 残った要素 4, 5, 6 を追加 -> 結果: [1, 2, 3, 4, 5, 6]
      • 最終結果: [1, 2, 3, 4, 5, 6]
    • 配列全体がソートされました。

  • コード例 (概念):
    “`
    function mergeSort(array):
    n = length of array
    if n <= 1:
    return array // 要素1個以下はソート済み

    mid = floor(n / 2)
leftHalf = mergeSort(array[0 to mid-1]) // 左半分を再帰的にソート
rightHalf = mergeSort(array[mid to n-1]) // 右半分を再帰的にソート

return merge(leftHalf, rightHalf) // ソートされた左右の半分をマージ

    function merge(left, right):
    result = []
    i = 0, j = 0
    while i < length of left and j < length of right:
    if left[i] <= right[j]: // 安定性を保つために <= とする
    append left[i] to result
    i = i + 1
    else:
    append right[j] to result
    j = j + 1
    // 残った要素を追加
    append remaining elements of left to result
    append remaining elements of right to result
    return result
    “`
    * 計算量:
    * 時間計算量:
    * 最良ケース: O(n log n)
    * 平均ケース: O(n log n)
    * 最悪ケース: O(n log n) (分割とマージのプロセスは入力順序に依存しない)
    * 空間計算量: O(n) (マージの過程で一時的な配列が必要となるため。in-placeではない)
    * 安定性: 安定
    * 長所: 時間計算量が常に O(n log n) であり、安定ソートである。外部ソートにも応用しやすい。
    * 短所: 追加のメモリ（O(n)）が必要。再帰呼び出しのオーバーヘッドがある。

5. クイックソート (Quick Sort)

  • 原理: 配列の中から一つ「ピボット（pivot）」となる要素を選びます。そして、ピボットより小さい要素を全てピボットの左側に、ピボットより大きい要素を全てピボットの右側に移動させます（パーティション分割）。この操作によって、ピボットは最終的にソートされた位置に配置されます。次に、ピボットの左側のサブ配列と右側のサブ配列に対して、再帰的にクイックソートを適用します。これも分割統治法に基づいています。

  • 動作 (図解):

    • 対象配列: [5, 2, 4, 6, 1, 3] (要素数 n=6)
    • 1回目のパーティション:
      • ピボットを選択します。ここでは簡単のため、最後の要素 3 をピボットとします。
      • 配列: [5, 2, 4, 6, 1, *3*]
      • 配列を走査し、ピボット 3 より小さい要素を左に集めます。
        • [5, 2, 4, 6, 1, 3]
        • 5 は 3 より大きい。
        • 2 は 3 より小さい。先頭（現在の位置）と交換する位置を維持しながら移動。
        • [2, 5, 4, 6, 1, 3] (概念的に、2を左側に移動)
        • 4 は 3 より大きい。
        • 6 は 3 より大きい。
        • 1 は 3 より小さい。左側に移動。
        • [2, 1, 4, 6, 5, 3] (概念的に、1を左側に移動)
      • パーティション終了後、ピボット 3 を、左側の「ピボットより小さい要素」のすぐ右に挿入します。
        • [2, 1] (3より小さい要素) [4, 6, 5] (3より大きい要素) [3] (ピボット)
        • ピボット 3 を [2, 1] と [4, 6, 5] の間に挿入します。
        • [2, 1, *3*, 4, 6, 5] (ピボット3が確定位置に)
      • これで、3 を基準に左側 ([2, 1]) と右側 ([4, 6, 5]) に分割されました。
    • 再帰呼び出し:
      • 左側のサブ配列 [2, 1] に対してクイックソートを適用します。
        • ピボットを 1 とします。
        • [2, *1*] -> [ ] (1より小さい) [2] (1より大きい) [*1*] (ピボット)
        • パーティション -> [*1*, 2]
        • サブ配列 [1, 2] はソートされました。
      • 右側のサブ配列 [4, 6, 5] に対してクイックソートを適用します。
        • ピボットを 5 とします。
        • [4, 6, *5*]
        • 4 は 5 より小さい -> [4] (5より小さい)
        • 6 は 5 より大きい -> [6] (5より大きい)
        • パーティション -> [4, *5*, 6]
        • サブ配列 [4, 5, 6] はソートされました。
    • 最終的な配列の状態: [1, 2, 3, 4, 5, 6]
    • 配列全体がソートされました。

  • コード例 (概念):
    “`
    function quickSort(array, low, high):
    if low < high:
    // パーティション分割
    pivotIndex = partition(array, low, high)

        // ピボットの左右のサブ配列に対して再帰的にソート
    quickSort(array, low, pivotIndex - 1)
    quickSort(array, pivotIndex + 1, high)

    function partition(array, low, high):
    pivot = array[high] // 最後の要素をピボットとする例
    i = low – 1 // 小さい要素の境界を示すインデックス

    for j from low to high - 1:
    if array[j] <= pivot:
        i = i + 1
        swap(array[i], array[j])

// ピボットを適切な位置 (i+1) に配置
swap(array[i + 1], array[high])
return i + 1 // ピボットの最終的なインデックス

    “`
    * 計算量:
    * 時間計算量:
    * 最良ケース (常に中央値付近をピボットに選べる): O(n log n)
    * 平均ケース: O(n log n)
    * 最悪ケース (常に最小値または最大値をピボットに選んでしまう – 例: 既にソート済み/逆順の配列で端の要素をピボットにする): O(n^2) (再帰呼び出しの深さが n になるため)
    * 空間計算量: O(log n) (平均ケース – 再帰呼び出しスタックの深さ) / O(n) (最悪ケース – 再帰呼び出しスタックの深さ)
    * 安定性: 不安定 (パーティション分割の際に要素の相対順序が変化する可能性がある)
    * 長所: 平均ケースで非常に高速。マージソートよりも空間計算量が少ない（平均 O(log n)）。in-placeソートとみなされることが多い。
    * 短所: 最悪ケースで O(n^2) となり性能が著しく低下する可能性がある。ピボット選択が性能に大きく影響する。安定ソートではない。

  • ピボット選択戦略: クイックソートの性能はピボットの選択に大きく依存します。最悪ケースを避けるために様々な戦略があります。

    • 常に先頭/末尾の要素を選ぶ (単純だが最悪ケースになりやすい)
    • ランダムな要素を選ぶ
    • 3つの要素（例: 先頭、中央、末尾）の中央値を選ぶ (Median-of-three)

6. ヒープソート (Heap Sort)

  • 原理: 配列を「ヒープ（Heap）」と呼ばれる特殊な木構造（バイナリヒープ）として扱い、ソートを行います。バイナリヒープは、親ノードの値が子ノードの値より常に大きい（または小さい）という性質を持ちます（最大ヒープまたは最小ヒープ）。ヒープソートは、まず配列を最大ヒープ構造に変換し、その後、ヒープの根（最大値）を取り出して配列の末尾に配置する操作を繰り返すことでソートを行います。

  • 動作 (図解):

    • 対象配列: [5, 2, 4, 6, 1, 3] (要素数 n=6)
    • ステップ 1: 最大ヒープを構築
      • 配列を完全バイナリツリーとみなします（インデックス0が根、インデックスiの子は2i+1と2i+2）。
      • [5, 2, 4, 6, 1, 3] を最大ヒープの性質を満たすように再配置します（heapify操作）。下から順に、親ノードが子ノードより大きくなるように調整します。
      • 最初の状態（ツリー構造で見ると根が5、左の子が2、右の子が4…）：
        5
        / \
        2 4
        / \ / \
        6 1 3
      • heapify操作によって最大ヒープ化すると（例：根は最大値である6）：
        6
        / \
        5 4
        / \ / \
        2 1 3
      • 配列の状態: [6, 5, 4, 2, 1, 3] (最大ヒープになった状態の一例)
    • ステップ 2: ソート (最大値の取り出しと再ヒープ化)
      • ヒープの根 (最大値 6) を配列の末尾要素 (3) と交換します。これで 6 は最終的な位置に確定します。
      • 配列の状態: [3, 5, 4, 2, 1, *6*] (最後の要素 6 はソート済み)
      • 残りの n-1 要素 ([3, 5, 4, 2, 1]) で再び最大ヒープを構築します（根 3 の位置から再帰的にheapify）。
      • 再ヒープ化後の配列（根が 5）：
        5
        / \
        3 4
        / \ /
        2 1
      • 配列の状態: [5, 3, 4, 2, 1, 6]
      • 再び、ヒープの根 (最大値 5) を未ソート部分の末尾要素 (1) と交換します。5 が確定します。
      • 配列の状態: [1, 3, 4, 2, *5*, 6] (最後の2要素 5, 6 はソート済み)
      • 残りの n-2 要素 ([1, 3, 4, 2]) で再び最大ヒープを構築します。
      • 再ヒープ化後の配列（根が 4）：
        4
        / \
        3 2
        /
        1
      • 配列の状態: [4, 3, 2, 1, 5, 6]
      • ヒープの根 (4) を未ソート部分の末尾 (1) と交換。4 が確定します。
      • 配列の状態: [1, 3, 2, *4*, 5, 6]
      • 残りの n-3 要素 ([1, 3, 2]) で再び最大ヒープを構築します。
      • 再ヒープ化後の配列（根が 3）：
        3
        / \
        1 2
      • 配列の状態: [3, 1, 2, 4, 5, 6]
      • ヒープの根 (3) を未ソート部分の末尾 (2) と交換。3 が確定します。
      • 配列の状態: [2, 1, *3*, 4, 5, 6]
      • 残りの n-4 要素 ([2, 1]) で再び最大ヒープを構築します。
      • 再ヒープ化後の配列（根が 2）：
        2
        /
        1
      • 配列の状態: [2, 1, 3, 4, 5, 6]
      • ヒープの根 (2) を未ソート部分の末尾 (1) と交換。2 が確定します。
      • 配列の状態: [1, *2*, 3, 4, 5, 6]
      • 最後の要素 1 が残りますが、これで配列全体がソートされました。

  • コード例 (概念):
    “`
    function heapSort(array):
    n = length of array

    // 1. 最大ヒープを構築 (葉ノード以外を下から順にheapify)
for i from floor(n / 2) - 1 down to 0:
    heapify(array, n, i)

// 2. ヒープから要素を一つずつ取り出し、ソート
for i from n - 1 down to 1:
    // 根 (最大値) と現在の末尾要素を交換
    swap(array[0], array[i])
    // 残りのヒープに対してheapify (サイズ i で根(0)から再調整)
    heapify(array, i, 0)
return array

    // array[i] を根とする部分木が最大ヒープになるように調整
    function heapify(array, heapSize, i):
    largest = i // largest を根として初期化
    left = 2 * i + 1 // 左の子
    right = 2 * i + 2 // 右の子

    // 左の子が largest より大きい場合
if left < heapSize and array[left] > array[largest]:
    largest = left

// 右の子が largest より大きい場合
if right < heapSize and array[right] > array[largest]:
    largest = right

// largest が根でない場合
if largest != i:
    swap(array[i], array[largest])
    // スワップによって影響を受けた部分木を再帰的にheapify
    heapify(array, heapSize, largest)

    “`
    * 計算量:
    * 時間計算量:
    * 最良ケース: O(n log n)
    * 平均ケース: O(n log n)
    * 最悪ケース: O(n log n) (ヒープ構築とheapify操作は常に O(log n) の計算量を持ち、それが n 回繰り返されるため)
    * 空間計算量: O(1) (追加のメモリは一時的な変数のみ)
    * 安定性: 不安定 (ヒープ化の過程で要素の相対順序が変わる可能性がある)
    * 長所: 時間計算量が常に O(n log n) であり、空間計算量が O(1) のin-placeソートである。
    * 短所: クイックソートやマージソートと比較して、一般的に定数倍の処理が遅い傾向がある。安定ソートではない。

特殊なソートアルゴリズム (線形時間ソート – O(n)系)

これらのアルゴリズムは、ソート対象のデータに特定の制約（例：要素が整数であり、その値の範囲が限定されている）がある場合に限り、要素数 n に対して線形時間 O(n) という非常に高速なソートを実現できます。比較ベースのソート（前述のアルゴリズムなど）は要素間の比較によって順序を決定するため、最速でも O(n log n) が限界であることが知られています。線形時間ソートは比較を行わない、あるいは比較以外の方法で順序を決定するため、この限界を超えられます。

7. 計数ソート (Counting Sort)

  • 原理: ソート対象の配列に含まれる各要素の値の出現頻度を数え上げ、その頻度情報をもとに元の配列をソートします。要素の値の範囲が分かっている場合に有効です。

  • 動作 (図解):

    • 対象配列: [5, 2, 4, 6, 1, 3] (要素数 n=6)
    • 要素の値の範囲は 1 から 6 です。
    • ステップ 1: 出現頻度を数える
      • 各要素の値 v に対して、その出現回数をカウントするための配列 count を用意します。count 配列のサイズは要素の最大値 + 1 (または最小値から最大値までの範囲 + 1) です。ここでは値の範囲が1-6なので、サイズ7の配列を用意し、インデックス1から6を使います。
      • count 配列を0で初期化: [0, 0, 0, 0, 0, 0, 0] (インデックス0から6)
      • 対象配列を走査し、各要素の値に対応する count 配列の要素をインクリメントします。
        • 5 を読む -> count[5] をインクリメント: [0, 0, 0, 0, 0, 1, 0]
        • 2 を読む -> count[2] をインクリメント: [0, 0, 1, 0, 0, 1, 0]
        • 4 を読む -> count[4] をインクリメント: [0, 0, 1, 0, 1, 1, 0]
        • 6 を読む -> count[6] をインクリメント: [0, 0, 1, 0, 1, 1, 1]
        • 1 を読む -> count[1] をインクリメント: [0, 1, 1, 0, 1, 1, 1]
        • 3 を読む -> count[3] をインクリメント: [0, 1, 1, 1, 1, 1, 1]
      • count 配列: [0, 1, 1, 1, 1, 1, 1] (値 1, 2, 3, 4, 5, 6 がそれぞれ1回出現)
    • ステップ 2: 累積和を計算
      • count 配列を、各値以下の要素が最終的にソート済み配列のどこに配置されるべきかを示すように累積和に変換します。
      • count[i] = count[i] + count[i-1]
      • [0, 1, 1, 1, 1, 1, 1] -> [0, 1, 2, 3, 4, 5, 6]
      • count 配列の意味: 値 1 は1つ目までの位置に、値 2 は2つ目までの位置に、…、値 6 は6つ目までの位置に配置される。
    • ステップ 3: ソート済み配列を構築
      • 元の配列 [5, 2, 4, 6, 1, 3] を後ろから走査します。ソート結果を格納するための出力配列 output (サイズ n=6) を用意します。
      • output 配列を0で初期化: [0, 0, 0, 0, 0, 0]
      • 元の配列の最後の要素 3 を読む。count[3] は 3 です。これは値 3 がソート済み配列の3番目（インデックス2）に配置されるべきことを示します。
        • output[count[3]-1]、つまり output[2] に 3 を配置します。output: [0, 0, 3, 0, 0, 0]
        • count[3] をデクリメントします: count: [0, 1, 2, 2, 4, 5, 6] (次に現れる 3 は 2番目の位置に配置されることを示す)
      • 元の配列の次の要素 1 を読む。count[1] は 1 です。output[count[1]-1]、つまり output[0] に 1 を配置します。
        • output: [1, 0, 3, 0, 0, 0]
        • count[1] をデクリメント: count: [0, 0, 2, 2, 4, 5, 6]
      • 元の配列の次の要素 6 を読む。count[6] は 6 です。output[count[6]-1]、つまり output[5] に 6 を配置します。
        • output: [1, 0, 3, 0, 0, 6]
        • count[6] をデクリメント: count: [0, 0, 2, 2, 4, 5, 5]
      • 元の配列の次の要素 4 を読む。count[4] は 4 です。output[count[4]-1]、つまり output[3] に 4 を配置します。
        • output: [1, 0, 3, 4, 0, 6]
        • count[4] をデクリメント: count: [0, 0, 2, 2, 3, 5, 5]
      • 元の配列の次の要素 2 を読む。count[2] は 2 です。output[count[2]-1]、つまり output[1] に 2 を配置します。
        • output: [1, 2, 3, 4, 0, 6]
        • count[2] をデクリメント: count: [0, 0, 1, 2, 3, 5, 5]
      • 元の配列の最初の要素 5 を読む。count[5] は 5 です。output[count[5]-1]、つまり output[4] に 5 を配置します。
        • output: [1, 2, 3, 4, 5, 6]
        • count[5] をデクリメント: count: [0, 0, 1, 2, 3, 4, 5]
      • 元の配列の走査が完了しました。output 配列にソート結果が得られました。
    • 最終結果: [1, 2, 3, 4, 5, 6]

  • コード例 (概念):
    “`
    function countingSort(array, maxValue): // maxValueは要素の最大値
    n = length of array
    count = array of size (maxValue + 1), initialized to 0
    output = array of size n, initialized to 0

    // 1. 出現頻度を数える
for i from 0 to n-1:
    count[array[i]] = count[array[i]] + 1

// 2. 累積和を計算
for i from 1 to maxValue:
    count[i] = count[i] + count[i-1]

// 3. 元の配列を後ろから走査し、ソート済み配列を構築
for i from n-1 down to 0:
    output[count[array[i]] - 1] = array[i]
    count[array[i]] = count[array[i]] - 1

// (オプション) 元の配列に結果をコピー
for i from 0 to n-1:
    array[i] = output[i]

return array // または output

    “`
    * 計算量:
    * 時間計算量: O(n + k) (nは要素数、kは要素の値の範囲のサイズ – max_value – min_value + 1)
    * 空間計算量: O(k) (count配列のための追加メモリ) + O(n) (output配列のための追加メモリ) = O(n + k)
    * 安定性: 安定 (元の配列を後ろから走査することで、同値要素の相対順序を保つことができる)
    * 長所: 要素の値の範囲 k が要素数 n に対して極端に大きくない場合、非常に高速 (O(n))。安定ソートである。
    * 短所: 要素の値が非負整数である必要があり、かつ値の範囲 k が小さい必要がある。値の範囲が非常に大きい場合、大量のメモリが必要になり、計算量も O(n + k) で k が支配的になってしまう。

8. 基数ソート (Radix Sort)

  • 原理: 要素を、数値の桁や文字列の文字など、固定された「基数」で表現できるものとみなし、最下位桁（または最下位文字）から順に、その桁の値に基づいて安定ソート（通常は計数ソートやバケットソート）を行います。全ての桁に対してこの操作を繰り返すと、最終的に配列全体がソートされます。

  • 動作 (図解):

    • 対象配列 (整数): [170, 45, 75, 90, 802, 24, 2, 66] (要素数 n=8)
    • 最大値は 802 で、3桁の数値です。最下位桁（1の位）から順にソートします。
    • ステップ 1: 1の位で安定ソート
      • 各要素を1の位の値でグループ分けします (0〜9)。
      • 安定ソート（例：計数ソート）を適用します。
      • 元の配列 [170, 45, 75, 90, 802, 24, 2, 66]
      • 1の位: 0, 5, 5, 0, 2, 4, 2, 6
      • ソート後 (1の位順): [170, 90, 802, 2, 24, 45, 75, 66]
    • ステップ 2: 10の位で安定ソート
      • ステップ1でソートされた配列 [170, 90, 802, 2, 24, 45, 75, 66] を、10の位の値で安定ソートします。
      • 10の位: 7, 9, 0, 0, 2, 4, 7, 6
      • ソート後 (10の位順): [802, 2, 24, 45, 66, 170, 75, 90]
    • ステップ 3: 100の位で安定ソート
      • ステップ2でソートされた配列 [802, 2, 24, 45, 66, 170, 75, 90] を、100の位の値で安定ソートします（100の位がない場合は0とみなします）。
      • 100の位: 8, 0, 0, 0, 0, 1, 0, 0
      • ソート後 (100の位順): [2, 24, 45, 66, 75, 90, 170, 802]
    • 全ての桁でソートが完了しました。配列全体がソートされています。
    • 最終結果: [2, 24, 45, 66, 75, 90, 170, 802]

  • コード例 (概念):
    “`
    function radixSort(array):
    // 最大値を見つけて桁数を判断 (例: 最大値 max = 802, 桁数は 3)
    max = findMax(array)
    // 最下位桁から最上位桁まで、各桁で安定ソート (countingSortを使用)
    for exp = 1; max / exp > 0; exp = exp * 10: // expは桁の値 (1, 10, 100, …)
    countingSortByDigit(array, exp) // expの桁に基づいてソート

    // countingSortByDigit: 指定された桁の値 exp に基づいて配列を安定ソート (計数ソートの改変版)
    function countingSortByDigit(array, exp):
    n = length of array
    output = array of size n, initialized to 0
    count = array of size 10, initialized to 0 // 桁の値は0-9

    // 1. 指定された桁の値の出現頻度を数える
for i from 0 to n-1:
    digit = (array[i] / exp) % 10 // exp桁目の値を取得
    count[digit] = count[digit] + 1

// 2. 累積和を計算
for i from 1 to 9:
    count[i] = count[i] + count[i-1]

// 3. 元の配列を後ろから走査し、ソート済み配列を構築
for i from n-1 down to 0:
    digit = (array[i] / exp) % 10
    output[count[digit] - 1] = array[i]
    count[digit] = count[digit] - 1

// 元の配列に結果をコピー
for i from 0 to n-1:
    array[i] = output[i]

// output は不要になる

    “`
    * 計算量:
    * 時間計算量: O(d * (n + k))。ここで、d は要素の最大桁数（またはキーの長さ）、n は要素数、k は各桁の基数（例: 10進数の場合は 10）。計数ソートが O(n+k) であり、それを d 回繰り返すため。要素の値の最大値が M の場合、10進数の桁数 d は log_10(M) に比例します。つまり、O(n log M) とも考えられます。要素が32ビット整数なら dは定数 (約10桁) とみなせるため、O(n) となります。
    * 空間計算量: O(n + k) または O(k)。使用する補助ソート（例: 計数ソート）の空間計算量に依存します。計数ソートを使う場合は O(n + k) です。
    * 安定性: 安定 (使用する補助ソートが安定であれば、基数ソートも安定となる)
    * 長所: 要素のデータ形式（整数、文字列など）によっては、非常に高速 (O(n)に近い) なソートが可能。
    * 短所: 比較ベースではないため、比較可能な任意のデータ型には適用できない。数値の場合は非負整数に限定されることが多い。キーの長さや基数によって性能が変動する。実装が比較的複雑。

その他のソートアルゴリズム (簡潔に)

  • バケットソート (Bucket Sort): 要素を値の範囲に基づいて複数の「バケット」に分配し、各バケット内の要素を個別にソート（必要なら再帰的にバケットソートや他のソートアルゴリズムを使用）した後、バケットを順番に結合するアルゴリズム。入力データが一様に分布している場合に高速で、平均計算量は O(n + k) となる（kはバケット数）。ただし、最悪ケースは O(n^2) となる可能性がある。
  • シェルソート (Shell Sort): 挿入ソートの改良版。離れた位置にある要素間である程度ソート（gapソート）を行い、徐々にそのギャップを小さくしていくことで、要素を大まかに正しい位置に移動させ、挿入ソートが効率的に行えるようにする。計算量はギャップの選択に依存するが、O(n log^2 n) や O(n^(3/2)) といった比較的高速なソートを実現できる場合がある。単純な O(n^2) ソートよりも高速だが、O(n log n) ソートよりは遅い。
  • ティムソート (Timsort): マージソートと挿入ソートを組み合わせたハイブリッドな安定ソートアルゴリズム。PythonやJavaの標準ライブラリで使われている。実世界のデータは既に部分的にソートされていることが多いという性質を利用し、マージソートの O(n log n) の最悪ケース性能と、挿入ソートの小さなデータやほぼソート済みのデータに対する高速性を組み合わせている。

どのソートアルゴリズムを選ぶべきか？

実際のプログラミングでは、特定の要件やデータの特性に応じて最適なソートアルゴリズムを選択することが重要です。

  • データ量が少ない場合: O(n^2) のアルゴリズム（挿入ソートなど）でも十分高速な場合が多いです。特に挿入ソートは、実装が簡単で、小さな配列やほぼソート済みの配列に対して高速です。
  • 大規模なデータで高速性が必要な場合: O(n log n) のアルゴリズムが候補になります。
    • クイックソート: 平均的に最も高速とされることが多く、空間効率も良い (平均 O(log n))。ただし、最悪ケース O(n^2) のリスクがあるため、ピボット選択戦略が重要になります。不安定ソートで問題ない場合に適しています。
    • マージソート: 時間計算量が常に O(n log n) であり、安定ソートであるという保証があります。外部ソートにも適していますが、O(n) の追加メモリが必要です。
    • ヒープソート: 常に O(n log n) の時間計算量と O(1) の空間計算量を持つ in-place ソートですが、一般的に他の O(n log n) ソートより少し遅いです。安定性は保証されません。
  • データの値に特定の制約がある場合:
    • 計数ソート: 要素が非負整数で、値の範囲が狭い場合に O(n) の超高速ソートが可能です。安定ソートでもあります。
    • 基数ソート: 要素が数値や文字列で、桁数（キーの長さ）が比較的短い場合に O(n) に近いソートが可能です。使用する補助ソートが安定であれば安定ソートとなります。
  • 安定性が必要な場合: マージソート、挿入ソート、計数ソート、基数ソート（安定な補助ソートを使用する場合）などが選択肢になります。クイックソートやヒープソートは不安定です。
  • ライブラリ関数を利用する場合: 多くのプログラミング言語の標準ライブラリに用意されているソート関数（例: C++ の std::sort、Java の Arrays.sort）は、単一のアルゴリズムではなく、複数のアルゴリズムを組み合わせた「ハイブリッドソート」であることが多いです。例えば、大規模データにはクイックソート系のアルゴリズム（ただし最悪ケースを防ぐ工夫がされている）、小規模データには挿入ソート、といった切り替えを行っています。特殊な要件がない限り、これらの最適化されたライブラリ関数を利用するのが最も効率的で安全な方法です。

まとめ：ソートアルゴリズムの旅を終えて

この記事では、コンピュータサイエンスにおける基本的ながら奥深いテーマであるソートアルゴリズムについて、その定義から始まり、評価基準、そして主要なアルゴリズムの原理、動作、計算量、長所・短所、安定性まで、詳細に解説しました。

学んだアルゴリズムを計算量の観点からまとめると以下のようになります（一般的な平均・最悪ケース）。

アルゴリズム 時間計算量 (平均/最悪) 空間計算量 安定性
バブルソート O(n^2) / O(n^2) O(1) 安定
選択ソート O(n^2) / O(n^2) O(1) 不安定
挿入ソート O(n^2) / O(n^2) O(1) 安定
マージソート O(n log n) / O(n log n) O(n) 安定
クイックソート O(n log n) / O(n^2) O(log n) / O(n) 不安定
ヒープソート O(n log n) / O(n log n) O(1) 不安定
計数ソート O(n + k) / O(n + k) O(n + k) 安定
基数ソート O(d * (n + k)) / O(d * (n + k)) O(n + k) / O(k) 安定*

*基数ソートの安定性は使用する補助ソートに依存。

ソートアルゴリズムの学習は、アルゴリズムの設計、解析、そして計算量の概念を理解する上で非常に重要です。それぞれのアルゴリズムがなぜ特定の性能を持つのか、どのようなトレードオフがあるのかを理解することで、より良いプログラム設計や問題解決能力に繋がります。

この記事を通じて、ソートアルゴリズムの多様性と奥深さを感じていただけたなら幸いです。実際のコーディングでは、多くの場合、言語に組み込まれた最適化されたソート関数を利用することになりますが、その背後にある原理を知っていることは、プログラムの性能を理解し、必要に応じて適切な手法を選択するために不可欠です。

これからも、様々なアルゴリズムやデータ構造について学びを深めていきましょう！

コメントする

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

上部へスクロール