アルゴリズム？プログラミング。 - クイックソート

Pythonで学ぶアルゴリズム　第21弾：並べ替え（クイックソート） - Qiita

最も早いとされるクイックソートです。

ある数字をもとに大小2つに分ける。これを繰り返していくいうちに並び替えが終わるというものです。このソートのミソは関数の中に関数を作って実行するという再帰というものです。

どんどん左側に小さな数字、右側には大きな数字が集まってきます。

ある数字をこの場合"pivot"

 pivot = data.pop(0) 

としてこの数字の大小でリストを分けます。ここでは内包表記でまとめて変数に入れていきます。leftには小さな数字、rightは大きな数字を振り分けます。

left = [i for i in data if i <= pivot]
right = [i for i in data if i > pivot]

内包表記ではなく、フィルターでも同じことができます。

   left = list(filter(lambda x: x <= pivot, data))
   right = list(filter(lambda x: x > pivot, data))

あとは再帰関数で繰り返し処理をさせます。

left = quick_sort(left)    
right = quick_sort(right)  

再帰でpivotを作り、大小のリストを作っていく方法で並び変えをしていきます。大の中に大小のリストという感じで細かくしていくことから並び替えができます。

最後に結果を戻してやります。

left + [pivot] + right

2つに分ける方法をいろいろ考えてみるのも面白いかも。

参考ページのコードは以下となっています。

def quick_sort(data):

    #分割できなくなる(リスト要素が1以下)であれば，そのままデータを返す(並べ替えの必要なし)
    if len(data) <= 1:
        return data

    pivot = data.pop(0) 
    print(pivot) #リストの先頭をピボットとして取り出す

    # ピボットより小さいものでリストを作る
    left = [i for i in data if i <= pivot]
    # ピボットより大きいものでリストを作る
    right = [i for i in data if i > pivot]

    print(left,right)

    left = quick_sort(left)       #入力に対する左側リストを形成する
    right = quick_sort(right)   #入力に対する右側リストを形成する

    #########再帰しきった結果のみ，quick_sort関数の出力として返される
    #########それ以外のreturnは上のleft = quick_sort(right), left = quick_sort(right)
    return left + [pivot] + right


DATA = [6, 15, 4, 2, 8, 5, 11, 9, 7, 13]

quick_sort(DATA)