Pythonでクイックソート実装

Scipyを学習するためのノートPython Scientific lecture notesというものが公開されています。英語版pdfはこちらの右上にあるDownloadsのところにあるpdfへのリンクを、日本語版pdfはこちらの上部にある印刷用のダウンロード書かれた横のpdfへのリンクをクリックすると読むことができます。ただし、(記事執筆時点では)日本語版は最新版ではないようです。

本日は英語版のノート24ページにある、Wikipediaのクイックソートの説明文(擬似コード)を実際のプログラムに変換せよという問題を解いてみました。以下、私の解答です。

# -*- encoding: utf-8 -*-

def quick_sort(array):
    if len(array) < 2:
        return array
    # 特に指定が無いのでほぼ中央の位置にある値をピボットとする
    pivot = array.pop(len(array)/2)
    less = []
    greater = []
    for x in array:
        if x < pivot + 1:
            less.append(x)
        else:
            greater.append(x)
    return quick_sort(less) + [pivot] + quick_sort(greater)

ピボットの選び方は簡単のため、リストの中央の位置にある値にしていますが、それ以外にも方法があります。例えば、中央の位置と両端の3つの値に対する中央値をピボットにするという方法があります。これは、クイックソートの性能はピボットの選び方に依存するためです。

極端ではありますが、毎回ピボット以下の値になるグループのデータ数が0、ピボットより値が大きいグループのデータが残り全部となった場合に効率が悪くなります。この場合、ソートのオーダはデータ数をnとしたときO(n^2)になります(1個ずつソート済になるため、バブルソートなどのソートと同じ程度の計算量になる)。クイックソートのオーダは平均してO(n*log(n))となるので、nが大きいとき非効率になってしまいます。

データを大きいもの、小さいもので半分ずつに分けられるようなピボットを選ぶのが理想的なのですが、データを大量に利用してピボット選択の計算をすること自体にも時間がかかってしまいます。このようなときは、ソートしたいデータの性質に依存したピボット選択を考えましょう。例えば、ほぼ昇順であるが、数パーセントのノイズが入ってくるデータの場合は、数パーセントのノイズには目をつぶって、中央の位置にある値(=ほぼ中央値と期待される)をピボットにするという方針を選ぶことが考えられます。

2012年9月14日追記

データの破壊はないほうがよいということなので、popメソッドを利用しない方針で書き直してみました。

# -*- encoding: utf-8 -*-

def quick_sort2(array):
    if len(array) < 2:
        return array
    # 特に指定が無いのでほぼ中央の位置にある値をピボットとする
    pivot_pos = len(array)/2
    pivot = array[pivot_pos]
    less = []
    greater = []
    for idx, x in enumerate(array):
        if idx == pivot_pos: continue
        if x < pivot + 1:
            less.append(x)
        else:
            greater.append(x)
    return quick_sort(less) + [pivot] + quick_sort(greater)