クイックソート | ソートアルゴリズム | アルゴリズムをはじめから

2024.10.21
スポンサーリンク
スポンサーリンク

クイックソートアルゴリズムの解説

クイックソートとは？

クイックソートは、高速なソートアルゴリズムの一つで、分割統治法（Divide and Conquer）を利用してデータを効率的に整列させます。リストから「ピボット」と呼ばれる基準となる要素を選び、そのピボットを使ってデータを2つのグループに分けます。ピボットより小さい要素と大きい要素に分けた後、それぞれのグループを再帰的にソートしていくことで、全体が整列されます。

クイックソートのステップ

  1. リストの中から1つのピボットを選びます（通常は真ん中の要素）。
  2. リストをピボットを基準にして、ピボットより小さい要素を左、大きい要素を右に分けます。
  3. 分割された各リストに対して、再帰的に同じ操作を繰り返します。
  4. リスト全体がソートされるまで、再帰的に分割とソートを繰り返します。

クイックソートのステップごとの変化

ステップ リストの状態 ピボット
初期状態 [5, 2, 9, 1, 5, 6] 5
1 [2, 1, 5] + [5] + [9, 6] 5
2 [1, 2] + [5] + [5, 6, 9] 5
3 [1, 2, 5, 5, 6, 9] —

クイックソートのJavaScript実装


// クイックソートのJavaScript実装
function quickSort(arr) {
    if (arr.length <= 1) return arr;

    let pivot = arr[Math.floor(arr.length / 2)];
    let left = [], right = [];

    for (let i = 0; i < arr.length; i++) {
        if (i !== Math.floor(arr.length / 2)) {
            arr[i] < pivot ? left.push(arr[i]) : right.push(arr[i]);
        }
    }

    return [...quickSort(left), pivot, ...quickSort(right)];
}

let array = [5, 2, 9, 1, 5, 6];
console.log("ソート前:", array);
console.log("ソート後:", quickSort(array));

クイックソートのPython実装

# クイックソートのPython実装
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)

array = [5, 2, 9, 1, 5, 6]
print("ソート前:", array)
print("ソート後:", quick_sort(array))

さらに詳しく

クイックソートの特徴は、その計算量が平均して O(n log n) と非常に効率的であることです。計算量というのは、アルゴリズムがデータ量に対してどれだけ効率的に動作するかを示す指標です。クイックソートの「分割統治法」は、データを再帰的に小さな部分に分割することで、計算の負担を減らす効果があります。しかし、最悪の場合、データが既に整列していたり、ピボットの選び方が悪いと O(n²) になる可能性もあります。

クイックソートは、データの性質に応じて非常に効果的に機能し、特に大量のデータを扱う場面でよく使われます。ピボットの選び方や実装に工夫を加えることで、より効率的なソートが可能です。

まとめ

クイックソートは効率的なソートアルゴリズムの一つであり、分割統治法に基づいた強力な手法です。計算量が O(n log n) であるため、大量のデータに対しても優れたパフォーマンスを発揮します。ピボットの選び方が重要なポイントとなりますが、理解しやすいアルゴリズムであり、特にパフォーマンスを重視する場面では広く使用されています。

スポンサーリンク