クイックソート

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

Miriam Antona

Software engineer

クイックソート

  • 分割統治法に基づく
  • 多くのプログラミング言語で実装済み
  • パーティション手法
    • ピボット
    • ピボットより小さい要素 ->
    • ピボットより大きい要素 ->
  • 左側再帰的に整列
  • 右側再帰的に整列
Pythonで学ぶデータ構造とアルゴリズム

クイックソート - 実行例

未整列の数値リストの模式図。

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

クイックソート - 実行例

未整列の数値リストの模式図。最初の要素が青。

  • Hoare のパーティション
Pythonで学ぶデータ構造とアルゴリズム

クイックソート - 実行例

未整列の数値リストの模式図。最初の要素が青。ポインタが2つ。左ポインタは2番目、右ポインタは最後を指す。

  • Hoare のパーティション
    • ピボットより大きい値に当たるまでポインタを進める
Pythonで学ぶデータ構造とアルゴリズム

クイックソート - 実行例

未整列の数値リストの模式図。最初の要素が青。ポインタが2つ。左ポインタは3番目、右ポインタは最後を指す。

  • Hoare のパーティション
    • ピボットより大きい値に当たるまでポインタを進める
Pythonで学ぶデータ構造とアルゴリズム

クイックソート - 実行例

未整列の数値リストの模式図。最初の要素が青。ポインタが2つ。左ポインタは3番目、右ポインタは5番目を指す。

  • Hoare のパーティション
    • ピボットより大きい値に当たるまでポインタを進める
    • ピボットより小さい値に当たるまでポインタを戻す
Pythonで学ぶデータ構造とアルゴリズム

クイックソート - 実行例

未整列の数値リストの模式図。最初の要素が青。ポインタが2つ。左ポインタは3番目、右ポインタは5番目を指す。3番目と5番目を交換する矢印がある。

  • Hoare のパーティション
    • ピボットより大きい値に当たるまでポインタを進める
    • ピボットより小さい値に当たるまでポインタを戻す
Pythonで学ぶデータ構造とアルゴリズム

クイックソート - 実行例

未整列の数値リストの模式図。最初の要素が青。ポインタが2つ。左ポインタは3番目、右ポインタは5番目を指す。3番目と5番目が交換済み。

  • Hoare のパーティション
    • ピボットより大きい値に当たるまでポインタを進める
    • ピボットより小さい値に当たるまでポインタを戻す
Pythonで学ぶデータ構造とアルゴリズム

クイックソート - 実行例

未整列の数値リストの模式図。最初の要素が青。ポインタが2つ。左ポインタは4番目、右ポインタは5番目を指す。

  • Hoare のパーティション
    • ピボットより大きい値に当たるまでポインタを進める
    • ピボットより小さい値に当たるまでポインタを戻す
Pythonで学ぶデータ構造とアルゴリズム

クイックソート - 実行例

未整列の数値リストの模式図。最初の要素が青。ポインタが2つ。左ポインタは4番目、右ポインタも4番目を指す。

  • Hoare のパーティション
    • ピボットより大きい値に当たるまでポインタを進める
    • ピボットより小さい値に当たるまでポインタを戻す
Pythonで学ぶデータ構造とアルゴリズム

クイックソート - 実行例

未整列の数値リストの模式図。最初の要素が青。ポインタが2つ。左ポインタは4番目、右ポインタは3番目を指す。

  • Hoare のパーティション
    • ピボットより大きい値に当たるまでポインタを進める
    • ピボットより小さい値に当たるまでポインタを戻す
Pythonで学ぶデータ構造とアルゴリズム

クイックソート - 実行例

未整列の数値リストの模式図。最初の要素が青。ポインタが2つ。左ポインタは4番目、右ポインタは3番目を指す。1番目と3番目を交換する矢印がある。

  • Hoare のパーティション
    • ピボットより大きい値に当たるまでポインタを進める
    • ピボットより小さい値に当たるまでポインタを戻す
Pythonで学ぶデータ構造とアルゴリズム

クイックソート - 実行例

未整列の数値リストの模式図。3番目の要素が青。1番目と3番目が交換済み。

  • Hoare のパーティション
    • ピボットより大きい値に当たるまでポインタを進める
    • ピボットより小さい値に当たるまでポインタを戻す
Pythonで学ぶデータ構造とアルゴリズム

クイックソート - 実行例

未整列の数値リストの模式図。3番目の要素が緑。

  • Hoare のパーティション
    • ピボットより大きい値に当たるまでポインタを進める
    • ピボットより小さい値に当たるまでポインタを戻す
Pythonで学ぶデータ構造とアルゴリズム

クイックソート - 実行例

未整列の数値リストの模式図。3番目が緑、左側の最初の2つが橙で左部分を示す。

  • Hoare のパーティション
    • ピボットより大きい値に当たるまでポインタを進める
    • ピボットより小さい値に当たるまでポインタを戻す
Pythonで学ぶデータ構造とアルゴリズム

クイックソート - 実行例

未整列の数値リストの模式図。1番目が青、2番目が橙、3番目が緑。左右のポインタは2番目を指す。

  • Hoare のパーティション
    • ピボットより大きい値に当たるまでポインタを進める
    • ピボットより小さい値に当たるまでポインタを戻す
Pythonで学ぶデータ構造とアルゴリズム

クイックソート - 実行例

未整列の数値リストの模式図。1番目が青、2番目が橙、3番目が緑。左右のポインタは2番目を指す。1番目と2番目を交換する矢印がある。

  • Hoare のパーティション
    • ピボットより大きい値に当たるまでポインタを進める
    • ピボットより小さい値に当たるまでポインタを戻す
Pythonで学ぶデータ構造とアルゴリズム

クイックソート - 実行例

未整列の数値リストの模式図。1番目が青、2番目が橙、3番目が緑。左右のポインタは2番目を指す。1番目と2番目が交換済み。

  • Hoare のパーティション
    • ピボットより大きい値に当たるまでポインタを進める
    • ピボットより小さい値に当たるまでポインタを戻す
Pythonで学ぶデータ構造とアルゴリズム

クイックソート - 実行例

未整列の数値リストの模式図。1番目が橙、2番目と3番目が緑。

  • Hoare のパーティション
    • ピボットより大きい値に当たるまでポインタを進める
    • ピボットより小さい値に当たるまでポインタを戻す
Pythonで学ぶデータ構造とアルゴリズム

クイックソート - 実行例

未整列の数値リストの模式図。1〜3番目が緑。

  • Hoare のパーティション
    • ピボットより大きい値に当たるまでポインタを進める
    • ピボットより小さい値に当たるまでポインタを戻す
Pythonで学ぶデータ構造とアルゴリズム

クイックソート - 実行例

未整列の数値リストの模式図。1〜3番目が緑。右側部分が橙。

  • Hoare のパーティション
    • ピボットより大きい値に当たるまでポインタを進める
    • ピボットより小さい値に当たるまでポインタを戻す
Pythonで学ぶデータ構造とアルゴリズム

クイックソート - 実行例

未整列の数値リストの模式図。1〜3番目が緑。右側の先頭が青。左ポインタは右側の2番目、右ポインタは右側の最後を指す。

  • Hoare のパーティション
    • ピボットより大きい値に当たるまでポインタを進める
    • ピボットより小さい値に当たるまでポインタを戻す
Pythonで学ぶデータ構造とアルゴリズム

クイックソート - 実行例

未整列の数値リストの模式図。1〜3番目が緑。右側の先頭が青。左右のポインタは右側の2番目を指す。

  • Hoare のパーティション
    • ピボットより大きい値に当たるまでポインタを進める
    • ピボットより小さい値に当たるまでポインタを戻す
Pythonで学ぶデータ構造とアルゴリズム

クイックソート - 実行例

未整列の数値リストの模式図。1〜3番目が緑。右側の先頭が青。左ポインタは右側の1番目、右ポインタは右側の2番目を指す。

  • Hoare のパーティション
    • ピボットより大きい値に当たるまでポインタを進める
    • ピボットより小さい値に当たるまでポインタを戻す
Pythonで学ぶデータ構造とアルゴリズム

クイックソート - 実行例

未整列の数値リストの模式図。1〜4番目が緑、5番目と6番目が橙。

  • Hoare のパーティション
    • ピボットより大きい値に当たるまでポインタを進める
    • ピボットより小さい値に当たるまでポインタを戻す
Pythonで学ぶデータ構造とアルゴリズム

クイックソート - 実行例

未整列の数値リストの模式図。1〜4番目が緑。要素が青。左右のポインタは最後の要素を指す。

  • Hoare のパーティション
    • ピボットより大きい値に当たるまでポインタを進める
    • ピボットより小さい値に当たるまでポインタを戻す
Pythonで学ぶデータ構造とアルゴリズム

クイックソート - 実行例

未整列の数値リストの模式図。1〜4番目が緑。要素が青。左右のポインタは最後の要素を指す。5番目と6番目を交換する矢印がある。

  • Hoare のパーティション
    • ピボットより大きい値に当たるまでポインタを進める
    • ピボットより小さい値に当たるまでポインタを戻す
Pythonで学ぶデータ構造とアルゴリズム

クイックソート - 実行例

未整列の数値リストの模式図。1〜4番目が緑。要素が青。左右のポインタは最後の要素を指す。5番目と6番目が交換済み。

  • Hoare のパーティション
    • ピボットより大きい値に当たるまでポインタを進める
    • ピボットより小さい値に当たるまでポインタを戻す
Pythonで学ぶデータ構造とアルゴリズム

クイックソート - 実行例

未整列の数値リストの模式図。すべての要素が整列済みのため緑。

  • Hoare のパーティション
    • ピボットより大きい値に当たるまでポインタを進める
    • ピボットより小さい値に当たるまでポインタを戻す
Pythonで学ぶデータ構造とアルゴリズム

クイックソート - 実装

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)
Pythonで学ぶデータ構造とアルゴリズム

クイックソート - 実装

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
Pythonで学ぶデータ構造とアルゴリズム

クイックソート - 実装

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]
Pythonで学ぶデータ構造とアルゴリズム

クイックソート - 計算量

  • 最悪: $O(n^2)$
  • とても高速
    • 平均: $\Theta(n\log{}n)$
    • 最良: $\Omega(n\log{}n)$
  • 空間計算量: $O(n\log{}n)$
Pythonで学ぶデータ構造とアルゴリズム

演習に進みましょう!

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

Preparing Video For Download...