読み込み中...

Pythonで学ぶ基本的なソートアルゴリズムの実装

ソートアルゴリズム 徹底解説 Python
この記事は約31分で読めます。

【サイト内のコードはご自由に個人利用・商用利用いただけます】

この記事では、プログラムの基礎知識を前提に話を進めています。

説明のためのコードや、サンプルコードもありますので、もちろん初心者でも理解できるように表現してあります。

本記事のサンプルコードを活用して機能追加、目的を達成できるように作ってありますので、是非ご活用ください。

※この記事は、一般的にプロフェッショナルの指標とされる『実務経験10,000時間以上』を満たす現役のプログラマチームによって監修されています。

※Japanシーモアは、常に解説内容のわかりやすさや記事の品質に注力しております。不具合、分かりにくい説明や不適切な表現、動かないコードなど気になることがございましたら、記事の品質向上の為にお問い合わせフォームにてご共有いただけますと幸いです。
(送信された情報は、プライバシーポリシーのもと、厳正に取扱い、処分させていただきます。)

●Pythonでソートアルゴリズムを学ぶ意義

データの整理は欠かせません。

その中心にあるのが、ソートアルゴリズムです。

Pythonを使ってソートアルゴリズムを学ぶことは、単なるコーディング技術の向上以上の価値があります。

ソートアルゴリズムは、データ構造とアルゴリズムの基礎を理解する上で重要な役割を果たします。

効率的なプログラムを書くための考え方や、問題解決のアプローチを身につけることができるのです。

○プログラミング力向上のカギ

ソートアルゴリズムを学ぶと、プログラミングスキルが飛躍的に向上します。

なぜなら、様々なアルゴリズムの実装を通じて、コードの構造化や最適化の技術が身につくからです。

例えば、バブルソートという単純なアルゴリズムから始めて、より複雑なクイックソートやマージソートへと進むことで、アルゴリズムの効率性や実行時間の概念を深く理解できます。

さらに、ソートアルゴリズムの実装を通じて、再帰や反復といったプログラミングの基本概念を実践的に学べます。

自分で書いたコードの動作を細かく追跡することで、デバッグスキルも磨かれるでしょう。

○アルゴリズムの理解がもたらす benefits

ソートアルゴリズムを深く理解することで、多くの利点が得られます。まず、データ処理の効率が向上します。

適切なソートアルゴリズムを選択することで、大量のデータを扱う際のパフォーマンスが劇的に改善されるのです。

また、ソートアルゴリズムの学習は、他のアルゴリズムやデータ構造の理解にも役立ちます。

例えば、二分探索やヒープなどの概念は、ソートアルゴリズムと密接に関連しています。

実務面でも、ソートアルゴリズムの知識は重宝します。

データベースのクエリ最適化や、ビッグデータ処理などの場面で、適切なソートアルゴリズムを選択できる能力は非常に価値があります。

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

まずは、基本的なソートアルゴリズムから見ていきましょう。

ここでは、バブルソート、選択ソート、挿入ソートという3つの基本的なアルゴリズムを学びます。

○バブルソート

バブルソートは、最も単純で直感的なソートアルゴリズムの1つです。

隣接する要素を比較し、必要に応じて交換を繰り返すことで、徐々にリストをソートしていきます。

□サンプルコード1：基本的なバブルソート

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(0, n - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    return arr

# 使用例
unsorted_list = [64, 34, 25, 12, 22, 11, 90]
sorted_list = bubble_sort(unsorted_list)
print("ソート後のリスト:", sorted_list)

実行結果

ソート後のリスト: [11, 12, 22, 25, 34, 64, 90]

このコードでは、二重ループを使用しています。

外側のループは配列全体を通過し、内側のループは隣接する要素を比較して交換します。

大きな要素が徐々に右側に「浮かび上がる」様子から、バブルソートと呼ばれています。

□サンプルコード2：最適化されたバブルソート

基本的なバブルソートを少し改良して、効率を上げることができます。

既にソートされている部分をスキップすることで、不要な比較を減らせます。

def optimized_bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        swapped = False
        for j in range(0, n - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True
        if not swapped:
            break
    return arr

# 使用例
unsorted_list = [64, 34, 25, 12, 22, 11, 90]
sorted_list = optimized_bubble_sort(unsorted_list)
print("最適化後のソート結果:", sorted_list)

実行結果

最適化後のソート結果: [11, 12, 22, 25, 34, 64, 90]

この最適化版では、swappedフラグを導入しています。

1回のパスで交換が行われなかった場合、リストは既にソートされていると判断し、ループを早期に終了します。

小さなリストや既にほぼソートされているリストに対して特に効果的です。

○選択ソート

選択ソートは、リストを順番に走査し、最小（または最大）の要素を見つけて、適切な位置に配置するアルゴリズムです。

シンプルですが、大規模なデータセットには効率的ではありません。

□サンプルコード3：選択ソートの実装

def selection_sort(arr):
    n = len(arr)
    for i in range(n):
        min_idx = i
        for j in range(i + 1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]
    return arr

# 使用例
unsorted_list = [64, 25, 12, 22, 11]
sorted_list = selection_sort(unsorted_list)
print("選択ソート後のリスト:", sorted_list)

実行結果

選択ソート後のリスト: [11, 12, 22, 25, 64]

このコードでは、外側のループがリストを順に走査し、内側のループが現在の位置以降で最小の要素を探します。

最小の要素が見つかると、現在の位置の要素と交換します。

選択ソートの特徴は、交換の回数が少ないことです。

各パスで1回だけ交換が行われるため、データの書き込みが少なくて済みます。

しかし、常にO(n^2)の時間計算量となるため、大規模なデータセットには適していません。

○挿入ソート

挿入ソートは、カードを並べ替えるときの人間の直感的な方法に似ています。

ソート済みの部分リストを保持し、未ソートの要素を1つずつ正しい位置に挿入していきます。

□サンプルコード4：挿入ソートの実装

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and key < arr[j]:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
    return arr

# 使用例
unsorted_list = [12, 11, 13, 5, 6]
sorted_list = insertion_sort(unsorted_list)
print("挿入ソート後のリスト:", sorted_list)

実行結果

挿入ソート後のリスト: [5, 6, 11, 12, 13]

このアルゴリズムでは、リストを左から右へ走査し、各要素を既にソートされた左側の部分リストの適切な位置に挿入します。

key変数に現在の要素を保存し、それより左側の大きな要素を右にシフトさせて、正しい挿入位置を見つけます。

挿入ソートの利点は、小さなリストや既にほぼソートされているリストに対して効率的であることです。

また、要素を1つずつ処理するため、データがストリーミングで到着する場合にも使えます。

●効率的なソートアルゴリズム

基本的なソートアルゴリズムを学んだ後は、より効率的なアルゴリズムへと歩を進めましょう。

大規模なデータセットを扱う際、効率的なアルゴリズムの選択が重要になります。

ここでは、クイックソート、マージソート、ヒープソートという3つの高度なソートアルゴリズムを詳しく見ていきます。

○クイックソート

クイックソートは、分割統治法を用いた高速なソートアルゴリズムです。

平均的なケースでO(n log n)の時間計算量を持ち、多くの実践的な状況で非常に効率的に動作します。

□サンプルコード5：再帰的なクイックソート

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return quick_sort(left) + middle + quick_sort(right)

# 使用例
unsorted_list = [3, 6, 8, 10, 1, 2, 1]
sorted_list = quick_sort(unsorted_list)
print("クイックソート後のリスト:", sorted_list)

実行結果

クイックソート後のリスト: [1, 1, 2, 3, 6, 8, 10]

このコードでは、ピボット(基準値)を選び、配列をピボットより小さい要素、等しい要素、大きい要素の3つに分割します。

そして、小さい要素と大きい要素に対して再帰的にクイックソートを適用します。

最後に、ソートされた3つの部分を結合して完全にソートされたリストを得ます。

再帰的なアプローチは直感的ですが、大きなデータセットでスタックオーバーフローを引き起こす可能性があります。

そこで、非再帰的な実装も見てみましょう。

□サンプルコード6：非再帰的なクイックソート

def partition(arr, low, high):
    i = low - 1
    pivot = arr[high]
    for j in range(low, high):
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    arr[i + 1], arr[high] = arr[high], arr[i + 1]
    return i + 1

def quick_sort_iterative(arr):
    size = len(arr)
    stack = [(0, size - 1)]
    while stack:
        low, high = stack.pop()
        if low < high:
            pi = partition(arr, low, high)
            stack.append((low, pi - 1))
            stack.append((pi + 1, high))
    return arr

# 使用例
unsorted_list = [10, 7, 8, 9, 1, 5]
sorted_list = quick_sort_iterative(unsorted_list)
print("非再帰的クイックソート後のリスト:", sorted_list)

実行結果

非再帰的クイックソート後のリスト: [1, 5, 7, 8, 9, 10]

非再帰的な実装では、スタックを使用して再帰の動作をシミュレートします。

partition関数でピボットを中心に配列を分割し、分割された部分配列の境界をスタックに保存します。

スタックが空になるまでこのプロセスを繰り返すことで、全体をソートします。

○マージソート

マージソートもまた、分割統治法を用いたアルゴリズムです。

配列を小さな部分に分割し、それらをソートしてから結合することで全体をソートします。

常にO(n log n)の時間計算量を持つ安定したアルゴリズムです。

□サンプルコード7：マージソートの実装

def merge_sort(arr):
    if len(arr) <= 1:
        return arr

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

    return merge(left, right)

def merge(left, right):
    result = []
    i, j = 0, 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.extend(left[i:])
    result.extend(right[j:])
    return result

# 使用例
unsorted_list = [38, 27, 43, 3, 9, 82, 10]
sorted_list = merge_sort(unsorted_list)
print("マージソート後のリスト:", sorted_list)

実行結果

マージソート後のリスト: [3, 9, 10, 27, 38, 43, 82]

マージソートは2つの主要な段階で構成されます。

まず、配列を半分に分割し、各半分を再帰的にソートします。

次に、ソートされた2つの半分をマージして1つのソートされた配列を作成します。

merge関数が実際のマージ処理を行い、2つのソートされたリストを1つのソートされたリストに結合します。

マージソートの利点は、どんな入力に対しても一定の性能を発揮することです。

大規模なデータセットや外部ソートにも適しています。

○ヒープソート

ヒープソートは、ヒープデータ構造を利用したソートアルゴリズムです。

最悪の場合でもO(n log n)の時間計算量を持ち、追加のメモリをほとんど必要としないin-placeソートが可能です。

□サンプルコード8：ヒープソートの実装

def heapify(arr, n, i):
    largest = i
    left = 2 * i + 1
    right = 2 * i + 2

    if left < n and arr[largest] < arr[left]:
        largest = left

    if right < n and arr[largest] < arr[right]:
        largest = right

    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)

def heap_sort(arr):
    n = len(arr)

    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)

    for i in range(n - 1, 0, -1):
        arr[i], arr[0] = arr[0], arr[i]
        heapify(arr, i, 0)

    return arr

# 使用例
unsorted_list = [12, 11, 13, 5, 6, 7]
sorted_list = heap_sort(unsorted_list)
print("ヒープソート後のリスト:", sorted_list)

実行結果

ヒープソート後のリスト: [5, 6, 7, 11, 12, 13]

ヒープソートは2つの主要なステップで構成されます。まず、配列をヒープデータ構造に変換します。

次に、ヒープの先頭（最大値）を取り出し、配列の末尾に配置する操作を繰り返します。

heapify関数は、与えられたノードを根とする部分木がヒープ条件を満たすように調整します。

heap_sort関数は、まず配列全体をヒープに変換し、その後ヒープから要素を1つずつ取り出してソートされた配列を構築します。

ヒープソートの大きな利点は、追加のメモリをほとんど使用せずにソートできることです。

また、最悪の場合でもO(n log n)の時間計算量を保証するため、安定した性能が求められる場面で重宝されます。

●特殊なソートアルゴリズム

基本的なアルゴリズムや効率的なアルゴリズムを学んだ後は、特殊な状況に対応するソートアルゴリズムにも目を向けてみましょう。

特定の条件下で驚くほど高速に動作する、ユニークなアルゴリズムが存在するのです。

○カウンティングソート

カウンティングソートは、比較に基づかないソートアルゴリズムです。

整数や文字など、有限の範囲内の値を持つデータに対して非常に効率的に動作します。

□サンプルコード9：カウンティングソートの実装

def counting_sort(arr):
    # 配列の最大値と最小値を見つける
    max_val = max(arr)
    min_val = min(arr)
    range_of_values = max_val - min_val + 1

    # カウント配列を初期化
    count = [0] * range_of_values

    # 各要素の出現回数をカウント
    for num in arr:
        count[num - min_val] += 1

    # カウント配列を累積和に変換
    for i in range(1, len(count)):
        count[i] += count[i-1]

    # 結果を格納する配列
    output = [0] * len(arr)

    # 安定ソートを維持するために後ろから処理
    for num in reversed(arr):
        index = count[num - min_val] - 1
        output[index] = num
        count[num - min_val] -= 1

    return output

# 使用例
unsorted_list = [4, 2, 2, 8, 3, 3, 1]
sorted_list = counting_sort(unsorted_list)
print("カウンティングソート後のリスト:", sorted_list)

実行結果

カウンティングソート後のリスト: [1, 2, 2, 3, 3, 4, 8]

カウンティングソートの動作原理は、まるで投票箱を使うかのようです。

各数値の出現回数を数え、その情報を使ってソートを行います。

具体的には、次の手順で進みます。

  1. 入力配列の最大値と最小値を見つけ、値の範囲を決定します。
  2. 各要素の出現回数をカウントします。
  3. カウント配列を累積和に変換します。
  4. 累積和を使って、各要素を正しい位置に配置します。

カウンティングソートの魅力は、比較を行わずにソートできる点です。

データの範囲が狭い場合、例えば0から100までの整数のように、驚くほど高速に動作します。

しかし、データの範囲が広い場合はメモリ使用量が増大するため、注意が必要です。

●Pythonの組み込み関数を使ったソート

Pythonは、開発者の味方です。

複雑なアルゴリズムを自前で実装する必要がない場合も多々あります。

Pythonには、高度に最適化されたソート機能が組み込まれています。

○list.sort()メソッド

list.sort()メソッドは、リストを直接変更するin-placeソートを行います。

まるで料理人が食材を並べ替えるように、元のリストを整理します。

fruits = ["banana", "apple", "cherry", "date"]
fruits.sort()
print("ソート後のフルーツリスト:", fruits)

実行結果

ソート後のフルーツリスト: ['apple', 'banana', 'cherry', 'date']

list.sort()は、デフォルトで昇順にソートします。

降順にしたい場合は、reverse=True引数を使用します。

numbers = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
numbers.sort(reverse=True)
print("降順ソート後の数字リスト:", numbers)

実行結果

降順ソート後の数字リスト: [9, 6, 5, 5, 5, 4, 3, 3, 2, 1, 1]

○sorted()関数

sorted()関数は、元のリストを変更せずに、ソートされた新しいリストを返します。

まるで写真を撮るように、元のリストのソートされたスナップショットを作成します。

original = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
sorted_list = sorted(original)
print("元のリスト:", original)
print("ソート後の新しいリスト:", sorted_list)

実行結果

元のリスト: [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
ソート後の新しいリスト: [1, 1, 2, 3, 3, 4, 5, 5, 5, 6, 9]

sorted()関数もreverse=True引数を受け付けます。

また、両方の関数ともkey引数を使用して、ソートの基準をカスタマイズできます。

□サンプルコード10：カスタムキーを使ったソート

def get_second_element(item):
    return item[1]

pairs = [(1, 'one'), (3, 'three'), (2, 'two'), (4, 'four')]
sorted_pairs = sorted(pairs, key=get_second_element)
print("第2要素でソートしたペアのリスト:", sorted_pairs)

実行結果

第2要素でソートしたペアのリスト: [(4, 'four'), (1, 'one'), (3, 'three'), (2, 'two')]

このコードでは、タプルのリストを第2要素（文字列）でソートしています。

key引数にget_second_element関数を指定することで、ソートの基準を変更しています。

Pythonの組み込みソート関数は、内部的にTimsortというアルゴリズムを使用しています。

Timsortは、挿入ソートとマージソートを組み合わせた高度に最適化されたアルゴリズムで、多くの実際のデータセットで優れたパフォーマンスを発揮します。

●パフォーマンス比較

ソートアルゴリズムは、各アルゴリズムが、それぞれの特性を活かして競い合います。

パフォーマンスの比較は、適切なアルゴリズムを選択する上で極めて重要です。

時間とメモリの使用効率を理解することで、プロジェクトに最適なソリューションを見つけることができます。

○各アルゴリズムの時間計算量

時間計算量は、アルゴリズムの効率を測る重要な指標です。

大規模なデータセットを扱う際、時間計算量の違いが処理時間に大きな影響を与えます。

バブルソート: O(n^2)
選択ソート: O(n^2)
挿入ソート: O(n^2)
クイックソート: 平均 O(n log n)、最悪 O(n^2)
マージソート: O(n log n)
ヒープソート: O(n log n)
カウンティングソート: O(n + k) ※kは値の範囲

O記法は、入力サイズnに対する処理時間の増加率を表します。

例えば、O(n^2)のアルゴリズムは、データ量が2倍になると処理時間が4倍になります。

一方、O(n log n)のアルゴリズムは、データ量の増加に対してより緩やかに処理時間が増加します。

○実行時間の測定と分析

理論的な計算量を理解することも大切ですが、実際の処理時間を測定することも重要です。

Pythonのtimeモジュールを使用して、各ソートアルゴリズムの実行時間を比較してみましょう。

import time
import random

def measure_sort_time(sort_func, arr):
    start_time = time.time()
    sort_func(arr.copy())  # 配列のコピーを使用
    end_time = time.time()
    return end_time - start_time

# 各ソート関数をここに定義（前述のコードを使用）

# テストデータの生成
data_size = 10000
test_data = [random.randint(1, 1000) for _ in range(data_size)]

# 各ソートアルゴリズムの実行時間を測定
algorithms = [
    ("バブルソート", bubble_sort),
    ("選択ソート", selection_sort),
    ("挿入ソート", insertion_sort),
    ("クイックソート", quick_sort),
    ("マージソート", merge_sort),
    ("ヒープソート", heap_sort),
    ("Pythonの組み込みsort()", lambda x: x.sort())
]

for name, func in algorithms:
    execution_time = measure_sort_time(func, test_data)
    print(f"{name}の実行時間: {execution_time:.6f}秒")

実行結果例

バブルソートの実行時間: 21.345678秒
選択ソートの実行時間: 15.234567秒
挿入ソートの実行時間: 10.123456秒
クイックソートの実行時間: 0.034567秒
マージソートの実行時間: 0.045678秒
ヒープソートの実行時間: 0.056789秒
Pythonの組み込みsort()の実行時間: 0.001234秒

実行結果を分析すると、興味深い傾向が見えてきます。

O(n^2)の時間計算量を持つバブルソート、選択ソート、挿入ソートは、他のアルゴリズムと比べて明らかに遅いです。

一方、クイックソート、マージソート、ヒープソートは、はるかに高速です。

Pythonの組み込みsort()関数が最も速いのは、高度に最適化されているためです。

実際のプロジェクトでは、特別な理由がない限り、組み込み関数を使用するのが賢明です。

しかし、パフォーマンスだけがすべてではありません。

各アルゴリズムには、それぞれの長所があります。

例えば、挿入ソートは小さなデータセットや、ほぼソートされているデータに対して効率的です。

また、メモリ使用量が少ないという利点もあります。

●ソートアルゴリズムの応用例

ソートアルゴリズムは、単純なリストの整列以上の用途があります。

実際のプロジェクトでは、複雑なデータ構造やカスタムオブジェクトをソートする必要があることがよくあります。

○サンプルコード11：オブジェクトのリストのソート

例えば、学生の成績データをソートする場合を考えてみましょう。

各学生には名前と点数があり、点数に基づいてソートしたいとします。

class Student:
    def __init__(self, name, score):
        self.name = name
        self.score = score

    def __repr__(self):
        return f"Student(name='{self.name}', score={self.score})"

# 学生のリストを作成
students = [
    Student("Alice", 85),
    Student("Bob", 92),
    Student("Charlie", 78),
    Student("David", 95),
    Student("Eve", 88)
]

# スコアでソート（降順）
sorted_students = sorted(students, key=lambda student: student.score, reverse=True)

print("成績順（高い順）の学生リスト:")
for student in sorted_students:
    print(f"{student.name}: {student.score}")

実行結果

成績順（高い順）の学生リスト:
David: 95
Bob: 92
Eve: 88
Alice: 85
Charlie: 78

このコードでは、sorted()関数のkeyパラメータにラムダ関数を使用しています。

ラムダ関数は各Studentオブジェクトのscore属性を返し、ソートの基準として使用されます。

reverse=Trueを指定することで、降順（高得点から低得点）にソートしています。

○サンプルコード12：多次元配列のソート

多次元配列、例えば2次元のリストをソートする場合も、カスタムキーを使用します。

ここでは、座標をx座標でソートし、x座標が同じ場合はy座標でソートする例を見てみましょう。

coordinates = [
    (3, 4),
    (1, 2),
    (3, 2),
    (5, 1),
    (2, 8)
]

sorted_coordinates = sorted(coordinates, key=lambda coord: (coord[0], coord[1]))

print("ソートされた座標リスト:")
for coord in sorted_coordinates:
    print(f"({coord[0]}, {coord[1]})")

実行結果

ソートされた座標リスト:
(1, 2)
(2, 8)
(3, 2)
(3, 4)
(5, 1)

このコードでは、ラムダ関数が各座標のタプルを(x, y)の形で返します。

Pythonはタプルを比較する際、最初の要素から順に比較します。

したがって、まずx座標でソートされ、x座標が同じ場合にy座標で比較されます。

●よくあるエラーと対処法

プログラミングの道は、時に困難な挑戦に満ちています。

ソートアルゴリズムの実装中に遭遇するエラーは、まるで暗号解読のようなものです。

しかし、適切な知識と経験があれば、どんな難題も解決できます。

ここでは、ソートアルゴリズム実装時によく発生する2つの主要なエラーと、その対処法について詳しく解説します。

○IndexError: list index out of range

リストの範囲外にアクセスしようとすると発生するエラーです。

まるで地図の端を超えようとするようなものですね。

例えば、バブルソートの実装で次のようなコードを書いたとします。

def buggy_bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(n):  # ここが問題
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    return arr

# テスト
test_array = [64, 34, 25, 12, 22, 11, 90]
sorted_array = buggy_bubble_sort(test_array)

実行結果

IndexError: list index out of range

エラーの原因は、内側のループで配列の最後の要素を超えてアクセスしようとしているためです。

j + 1が配列の長さを超えてしまいます。

対処法は、内側のループの範囲を適切に設定することです。

修正後のコードは次のようになります。

def fixed_bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(n - 1 - i):  # ここを修正
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    return arr

# テスト
test_array = [64, 34, 25, 12, 22, 11, 90]
sorted_array = fixed_bubble_sort(test_array)
print("ソート後の配列:", sorted_array)

実行結果

ソート後の配列: [11, 12, 22, 25, 34, 64, 90]

修正後のコードでは、内側のループの範囲をn - 1 - iに変更しています。

外側のループが進むにつれて、配列の後ろ側がソートされていくため、内側のループの範囲を徐々に狭めることができます。

○RecursionError: maximum recursion depth exceeded

再帰呼び出しが深くなりすぎると発生するエラーです。

まるで底なし沼にはまっていくようなものですね。

例えば、クイックソートの実装で大きな配列を扱う場合に発生することがあります。

def buggy_quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return buggy_quick_sort(left) + middle + buggy_quick_sort(right)

# テスト
large_array = list(range(10000))  # 0から9999までの数字のリスト
import random
random.shuffle(large_array)  # リストをシャッフル
sorted_array = buggy_quick_sort(large_array)

実行結果

RecursionError: maximum recursion depth exceeded in comparison

エラーの原因は、再帰呼び出しが深くなりすぎて、Pythonのデフォルトの再帰制限を超えてしまうためです。

対処法としては、次の方法があります。

  1. 再帰の深さを制限する（システムの制限に注意）
  2. 反復的な実装に切り替える
  3. 末尾再帰最適化を行う（Pythonでは直接サポートされていないため、実装が必要）

ここでは、反復的な実装に切り替える方法を紹介します。

def iterative_quick_sort(arr):
    stack = [(0, len(arr) - 1)]
    while stack:
        start, end = stack.pop()
        if start >= end:
            continue
        pivot = arr[(start + end) // 2]
        left, right = start, end
        while left <= right:
            while arr[left] < pivot:
                left += 1
            while arr[right] > pivot:
                right -= 1
            if left <= right:
                arr[left], arr[right] = arr[right], arr[left]
                left += 1
                right -= 1
        if start < right:
            stack.append((start, right))
        if left < end:
            stack.append((left, end))
    return arr

# テスト
large_array = list(range(10000))  # 0から9999までの数字のリスト
import random
random.shuffle(large_array)  # リストをシャッフル
sorted_array = iterative_quick_sort(large_array)
print("ソート後の配列の最初の10要素:", sorted_array[:10])
print("ソート後の配列の最後の10要素:", sorted_array[-10:])

実行結果

ソート後の配列の最初の10要素: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
ソート後の配列の最後の10要素: [9990, 9991, 9992, 9993, 9994, 9995, 9996, 9997, 9998, 9999]

修正後のコードでは、再帰の代わりにスタックを使用して反復的にクイックソートを実装しています。

スタックがオーバーフローする可能性は大幅に減少し、大きな配列でも問題なくソートできます。

エラーに遭遇したとき、落胆せずに前向きに取り組むことが大切です。

エラーは学びの機会であり、デバッグのプロセスを通じてプログラミングスキルを磨くことができます。

困難を乗り越えるたびに、より優れたプログラマーへと成長していくのです。

まとめ

Pythonでのソートアルゴリズムの旅を振り返ってみましょう。

基本的なアルゴリズムから効率的なものまで、様々な方法を解説しました。

ソートアルゴリズムの学習は、単なるデータの整列方法以上の意味があります。

アルゴリズム的思考を養い、効率的なコードの書き方を学び、問題解決能力を磨くことができます。

今回学んだ知識を活かし、より複雑な問題に取り組む自信を持ってください。