📛

クイックソートまとめ

2024/10/09に公開

 クイックソートとは？クイックソート（Quicksort）は、以下のような特徴を持つ効率的なソートアルゴリズムです：
基本原理:
分割統治法を用いたアルゴリズムです。
ピボット（基準値）を選び、配列をピボットより小さい要素と大きい要素に分割します。
アルゴリズムの流れ:
配列からピボットを選択します（多くの場合、最後の要素を使用）。
ピボットより小さい要素を左側に、大きい要素を右側に移動させます。
分割された部分配列に対して再帰的に同じ処理を適用します。
性能:
平均的な時間計算量: O(n log n)
最悪の場合の時間計算量: O(n^2)（ただし、ピボット選択を改善することで回避可能）
空間計算量: O(log n)（再帰呼び出しのためのスタック領域）
特徴:
インプレースソート：追加の大きなメモリ空間を必要としません。
不安定ソート：同じ値の要素の相対的な順序が保たれない可能性があります。

 インプレースソート(In-place sort)とはhttps://zenn.dev/btc/articles/241009_in_place_sort
利点:
平均的に非常に高速です。
キャッシュ効率が良いです。
インプレースで実装可能です。
欠点:
最悪の場合（既にソートされている配列など）のパフォーマンスが悪いです。
安定ソートではありません。
改善手法:
ランダムなピボット選択
三者中央値（median-of-three）によるピボット選択
小さな部分配列に対する挿入ソートの使用
クイックソートは、その高速性と効率性から、多くのプログラミング言語の標準ライブラリで採用されているソートアルゴリズムです。大規模なデータセットに対して特に効果的ですが、安定性が必要な場合や最悪のケースを回避する必要がある場合は、他のアルゴリズムの使用を検討する必要があります。

 コード例クイックソートの具体的なPythonコード例を以下に示します：
def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    else:
        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)

# 使用例
arr = [64, 34, 25, 12, 22, 11, 90]
print("ソート前:", arr)
sorted_arr = quick_sort(arr)
print("ソート後:", sorted_arr)
このコードの主な特徴は以下の通りです：
ピボットの選択:
配列の中央の要素をピボットとして選択しています。
分割:
リスト内包表記を使用して、ピボットより小さい要素（left）、ピボットと等しい要素（middle）、ピボットより大きい要素（right）に分割します。
再帰:
left と right の部分に対して再帰的にquick_sortを適用します。
基底ケース:
配列の長さが1以下の場合、そのまま返します。
結合:
ソートされたleft、middle、rightを結合して返します。
このアルゴリズムは、平均的にO(n log n)の時間計算量を持ちますが、最悪の場合（既にソートされている配列など）はO(n^2)になる可能性があります。また、この実装は追加のメモリを使用するため、厳密にはインプレースソートではありません。
実行結果は以下のようになります：
ソート前: [64, 34, 25, 12, 22, 11, 90]
ソート後: [11, 12, 22, 25, 34, 64, 90]
このコードは理解しやすく、Pythonの特徴を活かした実装になっていますが、大規模なデータセットに対しては、よりメモリ効率の良いインプレースな実装を検討する必要があります。

クイックソートとは？

インプレースソート(In-place sort)とは

コード例

Discussion