pythonでクイックソートを実装してみた

今回はソートアルゴリズムの中でも最速であるクイックソートをpythonで実装していきたいと思います．
実装部分に興味がある人は目次からクイックソートの実装を押して読み飛ばしてください.
目次

クイックソートとは

一般的に最も高速なソートアルゴリズムとして知られています．ただしデータの並びによってはO(n²)になってしまうアルゴリズムになっています．
クイックソートの動作としては

• 配列全体に対して以下の動作を繰り返す
  • ピボットを選ぶ(中央値がいいが今回は部分配列の最後の要素とする)

  • パーティションを用いて部分配列をさらに二つの部分配列にする

    1. パーティションの基準点をxとして配列の要素をiまでの範囲にx以下の要素をi+1からjまでの範囲にx以上の要素を移動させる．
    2. iまでの要素の配列とi+1からjまでの要素の配列の二つに分割する

基本的にピボットの選び方は中央値がいいのですが，その値を当てることはできないので一般的にはデータ列からランダムに持ってきたり，数個のデータの中央値をとったりするそうです．
また，対象となるデータ列が少なくなってきたら別のアルゴリズムを適用するなどしてクイックソートは利用されているそうです．(参照)
上記の動作の説明だけではわかりづらいと思うので下図を追いながら動作を確認してみてください．

パーティションの実装

クイックソートの中の動作に出てきたパーティションをまずは実装していきたいと思います．
パーティションの動きとしては

• ピボットを定める
• 配列番号iまでにピボットよりも小さな要素をまとめ，配列番号i+1以上にピボットより大きな要素をまとめる

これらをまずは実装していきたいと思います．

import random
def partition(A, start, end):
    pivot = A[end]
    i = start - 1
    for j in range(start, end):
        if A[j] <= pivot:
            #A[i+1]の要素はピボットより大きい要素なので
            #A[i+1]とピボット以下の大きさの要素A[j]の位置を入れ替える
            i += 1
            A[i], A[j] = A[j], A[i] 
    A.insert(i+1, pivot)
    A.pop()
    return 
        
        
A = list(range(1,11))
random.shuffle(A)
print(A)
partition(A, 0, len(A)-1)
print(A)

出力を確認すると

[1, 3, 8, 2, 4, 9, 5, 10, 7, 6]
[1, 3, 2, 4, 5, 6, 9, 8, 10, 7]

一番後ろにいた要素6(配列をシャッフルしているので実行の度に変わります)が配列の中の正しい位置に移動していると思います．
これでクイックソートの中核となる処理を作ることができました.

クイックソートの実装

続いて実際にクイックソートを実装していきたいと思います．
実装には先ほど作成したパーティションも活用します．
パーティションに関して一部コードを書き換えています．

import random
def partition(A, start, end):
    pivot = A[end]
    i = start - 1
    for j in range(start, end):
        if A[j] <= pivot:
            i += 1
            A[i], A[j] = A[j], A[i] 
    A[i+1], A[end] = A[end], A[i+1]
    print(A)
    return i+1
        
def quicksort(A, start, end):
    if start < end:
        pivot_position = partition(A, start, end)
        quicksort(A, start, pivot_position -1)
        quicksort(A,pivot_position + 1, end)
    
        
A = list(range(1,11))
random.shuffle(A)
print(A)
quicksort(A, 0, len(A)-1)
print(A)

出力例

[4, 10, 9, 2, 8, 1, 3, 6, 7, 5] # 初期配列
[4, 2, 1, 3, 5, 9, 10, 6, 7, 8] # pivot = 5
[2, 1, 3, 4, 5, 9, 10, 6, 7, 8] # pivot = 3
[1, 2, 3, 4, 5, 9, 10, 6, 7, 8] # pivot = 1
[1, 2, 3, 4, 5, 6, 7, 8, 10, 9] # pivot = 8
[1, 2, 3, 4, 5, 6, 7, 8, 10, 9] # pivot = 7
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10] # pivot = 9
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10] # ソート済み配列

徐々に配列がソートされていく様子がわかると思います．

コード解説

クイックソートの再帰関数部分を少しだけ補足しておきます．
" if start < end "の部分は部分配列の要素が一つ以下，すなわち，pivotの位置の前後に要素が一つ以下の状態で止まるようになっています．
残りのコード部分に関しては

• ピボットの位置より前にある要素で再度パーティションを行う
• ピボットの位置より後ろにある要素で再度パーティションを行う

という処理を行なっているだけです．
パーティションの実装ができ，再帰関数の扱い方に慣れていれば意外と簡単に実装できますね．

もっとこんな実装があるよとかこれを実装してみて欲しいというようなものがあればコメントください！