クイックソート

Pythonで学ぶデータ構造とアルゴリズム

Miriam Antona

Software engineer

クイックソート

分割統治法に基づく
多くのプログラミング言語で実装されている
パーティション手法
- ピボット
- ピボットより小さい項目 -> 左
- ピボットより大きい項目 -> 右
左側の要素に再帰的にソートが呼び出される
右側の要素に再帰的にソートが呼び出される

クイックソート - 実行

順不同の番号が並んだリスト。

クイックソート - 実行

順不同の番号が並んだリスト。最初の要素は青色で表示されている。

ホーアのパーティション

クイックソート - 実行

順不同の番号が並んだリスト。最初の要素は青色で表示されている。 2つのポインターがある。左のポインターは2番目の要素を指し、右のポインターは最後の要素を指している

ホーアのパーティション
- ピボットより大きい値が見つかるまで、左ポインタを移動する

クイックソート - 実行

順不同の番号が並んだリスト。最初の要素は青色で表示されている。 2つのポインターがある。左のポインターは3番目の要素を指し、右のポインターは最後の要素を指している。

ホーアのパーティション
- ピボットより大きい値が見つかるまで、左ポインタを移動する

クイックソート - 実行

順不同の番号が並んだリスト。最初の要素は青色で表示されている。 2つのポインターがある。左のポインターは3番目の要素を指し、右のポインターは5番目の要素を指している。

ホーアのパーティション方式
- ピボットより大きい値が見つかるまで、左ポインタを移動する
- ピボットより小さい値が見つかるまで、右ポインタを移動する

クイックソート - 実行

順不同の番号が並んだリスト。最初の要素は青色で表示されている。 2つのポインターがある。左のポインタは3番目の要素を指し、右のポインタは5番目の要素を指している。 2つの矢印は、3番目と5番目の要素が入れ替わることを示している。

ホーアのパーティション方式
- ピボットより大きい値が見つかるまで、左ポインタを移動する
- ピボットより小さい値が見つかるまで、右ポインタを移動する

クイックソート - 実行

順不同の番号が並んだリスト。最初の要素は青色で表示されている。 2つのポインターがある。左のポインタは3番目の要素を指し、右のポインタは5番目の要素を指している。 3番目と5番目の要素が入れ替わっている。

ホーアのパーティション方式
- ピボットより大きい値が見つかるまで、左ポインタを移動する
- ピボットより小さい値が見つかるまで、右ポインタを移動する

クイックソート - 実行

順不同の番号が並んだリスト。最初の要素は青色で表示されている。 2つのポインターがある。左のポインターは4番目の要素を指し、右のポインターは5番目の要素を指している。

ホーアのパーティション方式
- ピボットより大きい値が見つかるまで、左ポインタを移動する
- ピボットより小さい値が見つかるまで、右ポインタを移動する

クイックソート - 実行

順不同の番号が並んだリスト。最初の要素は青色で表示されている。 2つのポインターがある。左のポインターは4番目の要素を指し、右のポインターは4番目の要素を指している。

ホーアのパーティション
- ピボットより大きい値が見つかるまで、左ポインタを移動する
- ピボットより小さい値が見つかるまで、右ポインタを移動する

クイックソート - 実行

順不同の番号が並んだリスト。最初の要素は青色で表示されている。 2つのポインターがある。左のポインターは4番目の要素を指し、右のポインターは3番目の要素を指している。

ホーアのパーティション
- ピボットより大きい値が見つかるまで、左ポインタを移動する
- ピボットより小さい値が見つかるまで、右ポインタを移動する

クイックソート - 実行

順不同の番号が並んだリスト。最初の要素は青色で表示されている。 2つのポインターがある。左のポインターは4番目の要素を指し、右のポインターは3番目の要素を指している。最初の要素と3番目の要素が入れ替わることを示す2本の矢印がある。

ホーアのパーティション
- ピボットより大きい値が見つかるまで、左ポインタを移動する
- ピボットより小さい値が見つかるまで、右ポインタを移動する

クイックソート - 実行

順不同の番号が並んだリスト。 3つ目の要素は青色で表示されている。最初の要素と3番目の要素が入れ替わっている。

ホーアのパーティション
- ピボットより大きい値が見つかるまで、左ポインタを移動する
- ピボットより小さい値が見つかるまで、右ポインタを移動する

クイックソート - 実行

順不同の番号が並んだリスト。 3つ目の要素は緑色で表示されている。

ホーアのパーティション
- ピボットより大きい値が見つかるまで、左ポインタを移動する
- ピボットより小さい値が見つかるまで、右ポインタを移動する

クイックソート - 実行

順不同の番号が並んだリスト。 3つ目の要素は緑色で、最初の2つの要素はオレンジ色で表示され、リストの左側部分を表している。

ホーアのパーティション
- ピボットより大きい値が見つかるまで、左ポインタを移動する
- ピボットより小さい値が見つかるまで、右ポインタを移動する

クイックソート - 実行

順不同の番号が並んだリスト。最初の要素は青、2番目の要素はオレンジ、3番目の要素は緑。左と右のポインターは2番目の要素を指している。

ホーアのパーティション
- ピボットより大きい値が見つかるまで、左ポインタを移動する
- ピボットより小さい値が見つかるまで、右ポインタを移動する

クイックソート - 実行

順不同の番号が並んだリスト。最初の要素は青、2番目の要素はオレンジ、3番目の要素は緑。左と右のポインターは2番目の要素を指している。最初の要素と2番目の要素が入れ替わることを示す2つの行がある。

ホーアのパーティション
- ピボットより大きい値が見つかるまで、左ポインタを移動する
- ピボットより小さい値が見つかるまで、右ポインタを移動する

クイックソート - 実行

順不同の番号が並んだリスト。最初の要素は青、2番目の要素はオレンジ、3番目の要素は緑。左と右のポインターは2番目の要素を指している。最初の要素と2番目の要素が入れ替わっている。

ホーアのパーティション
- ピボットより大きい値が見つかるまで、左ポインタを移動する
- ピボットより小さい値が見つかるまで、右ポインタを移動する

クイックソート - 実行

順不同の番号が並んだリスト。最初の要素はオレンジ色、2番目と3番目の要素は緑色。

ホーアのパーティション
- ピボットより大きい値が見つかるまで、左ポインタを移動する
- ピボットより小さい値が見つかるまで、右ポインタを移動する

クイックソート - 実行

順不同の番号が並んだリスト。最初、2番目、3番目の要素は緑色で表示されている。

ホーアのパーティション
- ピボットより大きい値が見つかるまで、左ポインタを移動する
- ピボットより小さい値が見つかるまで、右ポインタを移動する

クイックソート - 実行

順不同の番号が並んだリスト。最初、2番目、3番目の要素は緑色で表示されている。リストの右側はオレンジ色で表示されている。

ホーアのパーティション
- ピボットより大きい値が見つかるまで、左ポインタを移動する
- ピボットより小さい値が見つかるまで、右ポインタを移動する

クイックソート - 実行

順不同の番号が並んだリスト。最初、2番目、3番目の要素は緑色で表示されている。右側の最初の要素は青色で表示されている。左のポインタは右側の2番目の要素を指し、右のポインタは右側の最後の要素を指している。

ホーアのパーティション
- ピボットより大きい値が見つかるまで、左ポインタを移動する
- ピボットより小さい値が見つかるまで、右ポインタを移動する

クイックソート - 実行

順不同の番号が並んだリスト。最初、2番目、3番目の要素は緑色で表示されている。右側の最初の要素は青色で表示されている。左と右のポインターは、リスト右側の2番目の要素を指している。

ホーアのパーティション
- ピボットより大きい値が見つかるまで、左ポインタを移動する
- ピボットより小さい値が見つかるまで、右ポインタを移動する

クイックソート - 実行

順不同の番号が並んだリスト。最初、2番目、3番目の要素は緑色で表示されている。右側の最初の要素は青色で表示されている。左のポインタは右側の最初の要素を指し、右のポインタは右側の2番目の要素を指している。

ホーアのパーティション
- ピボットより大きい値が見つかるまで、左ポインタを移動する
- ピボットより小さい値が見つかるまで、右ポインタを移動する

クイックソート - 実行

順不同の番号が並んだリスト。最初、2番目、3番目、4番目の要素は緑色で、5番目と6番目の要素はオレンジ色。

ホーアのパーティション
- ピボットより大きい値が見つかるまで、左ポインタを移動する
- ピボットより小さい値が見つかるまで、右ポインタを移動する

クイックソート - 実行

順不同の番号が並んだリスト。最初、2番目、3番目、4番目の要素は緑色で表示されている。要素は青色で表示されている。左と右のポインターは最後の要素を指している。

ホーアのパーティション
- ピボットより大きい値が見つかるまで、左ポインタを移動する
- ピボットより小さい値が見つかるまで、右ポインタを移動する

クイックソート - 実行

順不同の番号が並んだリスト。最初、2番目、3番目、4番目の要素は緑色で表示されている。要素は青色で表示されている。左と右のポインターは最後の要素を指している。 5番目と6番目の要素が入れ替わることを示す2本の矢印がある。

ホーアのパーティション
- ピボットより大きい値が見つかるまで、左ポインタを移動する
- ピボットより小さい値が見つかるまで、右ポインタを移動する

クイックソート - 実行

順不同の番号が並んだリスト。最初、2番目、3番目、4番目の要素は緑色で表示されている。要素は青色で表示されている。左と右のポインターは最後の要素を指している。 5番目と6番目の要素が入れ替わっている。

ホーアのパーティション
- ピボットより大きい値が見つかるまで、左ポインタを移動する
- ピボットより小さい値が見つかるまで、右ポインタを移動する

クイックソート - 実行

順不同の番号が並んだリスト。すべての要素はソートされているため、緑色で表示されている。

ホーアのパーティション
- ピボットより大きい値が見つかるまで、左ポインタを移動する
- ピボットより小さい値が見つかるまで、右ポインタを移動する

クイックソート - 実装

def quicksort(my_list, first_index, last_index):

    if first_index < last_index:

        partition_index = partition(my_list, first_index, last_index)

        quicksort(my_list, first_index, partition_index)

        quicksort(my_list, partition_index + 1, last_index)

クイックソート - 実装

def partition(my_list, first_index, last_index):

    pivot = my_list[first_index]
    left_pointer = first_index + 1
    right_pointer = last_index

    while True: 
        while my_list[left_pointer] < pivot and left_pointer < last_index:
            left_pointer += 1

        while my_list[right_pointer] > pivot and right_pointer >= first_index:
            right_pointer -= 1

        if left_pointer >= right_pointer:
            break

        my_list[left_pointer], my_list[right_pointer] = my_list[right_pointer], my_list[left_pointer]

    my_list[first_index], my_list[right_pointer] = my_list[right_pointer], my_list[first_index]

    return right_pointer

クイックソート - 実装

my_list = [6, 2, 9, 7, 4, 8] 
quicksort(my_list, 0, len(my_list) - 1)
print(my_list)

[2, 4, 6, 7, 8, 9]

クイックソート - 計算量

最悪：$O(n^2)$
非常に効率的！
- 平均：$\Theta(n\log{}n)$
- 最良：$\Omega(n\log{}n)$
空間計算量：$O(n\log{}n)$

練習しましょう！

Pythonで学ぶデータ構造とアルゴリズム