クイックソート

1. 概要

クイックソートは名前の通り、高速にソートを行えます。

2. コード

コピペで実行できます。

簡単なもの

クイックソートは、基準になる値を１つ決め、 それより大きい値のグループと小さい値のグループに分けます。 そしてこの作業を繰り返し、ソートされたリストを得ます。

#
# 対話モード >>> に
# コピペで実行できます。
#
def linked_quick_sort(lst):
    if not lst:
        return
    #
    # 1. 分割
    #
    smaller = []
    pivot = lst.pop()
    bigger = []
    while lst:
        e = lst.pop()
        if e <= pivot:
            smaller.append(e)
        else:
            bigger.append(e)
    
    #
    # 2. ソート
    #
    linked_quick_sort(smaller)
    linked_quick_sort(bigger)
    
    #
    # 3. 結合　
    #
    smaller.reverse()
    while smaller:
        lst.append(smaller.pop())
    lst.append(pivot)
    bigger.reverse()
    while bigger:
        lst.append(bigger.pop())


lst = [8, 3, 1, 6, 10, 4, 7, 14, 13]
linked_quick_sort(lst)
print(lst)
# [1, 3, 4, 6, 7, 8, 10, 13, 14]

Python で quicksort - Qiita

Qiita の記事の方がシンプルな書き方です。 pop, append を使い書きました。 これは次で示す添字表記 lst[i] と対比させるためです。

マージソート、ヒープソートでも pop, append を使ったものと 添字表記 lst[i] のものを対比して書いています。

難しいもの

#
# 対話モード >>> に
# コピペで実行できます。
#
def quick_sort(lst):
    _quick_sort(lst, 0, len(lst) - 1)


def _quick_sort(lst, begin, end):
    if begin == end + 1:
        return
    
    #
    # 1. 分割
    #
    left, right = begin, end
    pivot = lst[end]
    
    # **大事**
    #   pivot を番兵にしている
    #   これがないと right が begin を突き抜けて
    #   リストを一周してしまう
    lst[left], lst[right] = lst[right], lst[left]
    
    while True:
        while lst[left] < pivot:
            left = left + 1
        while pivot < lst[right]:
            right = right - 1
        if right <= left:
            break
        lst[left], lst[right] = lst[right], lst[left]
        left = left + 1
        right = right - 1
    
    #
    # 2. ソート
    #
    _quick_sort(lst, begin, left - 1)
    _quick_sort(lst, right + 1, end)


lst = [3333, 5123, 9981, 1243, 7412]
quick_sort(lst)
print(lst)
# [1243, 3333, 5123, 7412, 9981]

番兵 (opens new window) という言葉は、 頭の片隅にあってもいい言葉かもしれません。

Photo by Leo Rivas

過程

本当にちゃんと実装したの？って感じなので、 途中結果を表示するコードを書きました。

#
# 対話モード >>> に
# コピペで実行できます。
#
def quick_sort(lst):
    _quick_sort(lst, 0, len(lst) - 1)


def _quick_sort(lst, begin, end):
    if begin == end + 1:
        return
    
    #
    # 1. 分割
    #
    left, right = begin, end
    pivot = lst[end]
    
    # **大事**
    #   pivot を番兵にしている
    #   これがないと right が begin を突き抜けて
    #   リストを一周してしまう
    lst[left], lst[right] = lst[right], lst[left]
    
    while True:
        while lst[left] < pivot:
            left = left + 1
        while pivot < lst[right]:
            right = right - 1
        if right <= left:
            break
        lst[left], lst[right] = lst[right], lst[left]
        left = left + 1
        right = right - 1
    
    print_progress(lst, begin, left, end)
    
    #
    # 2. ソート
    #
    _quick_sort(lst, begin, left - 1)
    _quick_sort(lst, right + 1, end)


def print_progress(lst, *args):
    print(' '.join(f'{e:2d}' for e in lst))
    print(' '.join(progress(lst, *args)))
    print()

def progress(lst, begin, pivot_index, end):
    n = len(lst)
    prog = []
    prog = prog + ['  '] * begin
    prog = prog + ['<<'] * (pivot_index - begin)
    prog = prog + ['pv']
    prog = prog + ['>>'] * (end - pivot_index)
    prog = prog + ['  '] * (n - end - 1)
    return prog


import random
lst = [random.randint(0, 99) for i in range(16)]
quick_sort(lst)
print(lst)

実行結果は以下のようになります。 ランダムな整数 16 個を作成して途中結果を表示します。 コメントは手書きで付け加えました。

# 最初のリストです。
# 基準となる値 pivot はリストの末尾が選ばれます。
# 50 が pivot になります。
14 33 40 71 75 80 48 27 93  3 36 77 19 70 27 50

# 50 を基準にして
# 小さい数は左に
# 大きい数は右に分かれました。
# 次は 27 が pivot になります。
14 33 40 48 27  3 36 19 27 50 70 77 93 80 75 71
<< << << << << << << << << pv >> >> >> >> >> >>

# 27 を基準にして
# 小さい数は左に
# 大きい数は右に分かれました。
# 次は 19 が pivot になります。
14  3 19 27 36 27 48 40 33 50 70 77 93 80 75 71
<< << << pv >> >> >> >> >>                     

# 19 を基準にして
# 小さい数は左に
# 大きい数は右に分かれました。
# 次は 3 が pivot になります。
14  3 19 27 36 27 48 40 33 50 70 77 93 80 75 71
<< << pv                                       

# 19 を基準にして
# 小さい数は左に
# 大きい数は右に分かれました。
# 左には数はないので右に移ります。
 3 14 19 27 36 27 48 40 33 50 70 77 93 80 75 71
pv >>                                          

# 14 は１つだけ
 3 14 19 27 36 27 48 40 33 50 70 77 93 80 75 71
   pv                                          

# 再帰を遡り
# 27 が pivot であった時の
# 右側をまた２つに分けていきます。
 3 14 19 27 27 33 40 48 36 50 70 77 93 80 75 71
            << pv >> >> >>                     

# 以下繰り返しです。
 3 14 19 27 27 33 40 48 36 50 70 77 93 80 75 71
            pv                                 

 3 14 19 27 27 33 36 48 40 50 70 77 93 80 75 71
                  pv >> >>                     

 3 14 19 27 27 33 36 40 48 50 70 77 93 80 75 71
                     pv >>                     

 3 14 19 27 27 33 36 40 48 50 70 77 93 80 75 71
                        pv                     

 3 14 19 27 27 33 36 40 48 50 70 71 75 80 93 77
                              << pv >> >> >> >>

 3 14 19 27 27 33 36 40 48 50 70 71 75 80 93 77
                              pv               

 3 14 19 27 27 33 36 40 48 50 70 71 75 77 93 80
                                    << pv >> >>

 3 14 19 27 27 33 36 40 48 50 70 71 75 77 93 80
                                    pv         

 3 14 19 27 27 33 36 40 48 50 70 71 75 77 80 93
                                          pv >>

 3 14 19 27 27 33 36 40 48 50 70 71 75 77 80 93
                                             pv

 3 14 19 27 27 33 36 40 48 50 70 71 75 77 80 93

おわりに

クイックソートは一見して難しそうですが、 大きいものと小さいものに分けて、 最終的に分けられたものが１つだけになったら、 切り戻ってきます。 二分探索木をイメージがあると理解しやすいかなと思います。

読めてませんが、鬼のようにとてもよくまとまっています。

• ソートを極める！ - Qiita (opens new window)

ここまでくると高速でメモリを消費しないヒープソートに軍配が上がりそうですが、 ヒープソートは安定ソートではないそうです。 安定ソートという言葉があるので、 ここまで来られたら、頭の片隅に置いておいてもいいかもしれません。

• 安定ソート - Wikipedia (opens new window)

高速かつ安定なアルゴリズム TimSort とは、 どのようなものなのでしょうか。

• 高速な安定ソートアルゴリズム TimSort の解説 (opens new window)