Webページでは数式を表すためにLaTeX表記が使えるMathJaxを利用しています。 WebブラウザにはSafari/Chrome/Firefoxを使って下さい（IEでは表示できないようです。）

並べ替えのアルゴリズム

安定な並び替え（stable sort）とは、レコードデータ中に同一キーを持つレコードが複数ある場合、並べ替えた後に並べ替え前のレコードの順序関係が維持されるということである。 並べ替えることで、並べ替え前の位置関係が崩れるような並べ替えを不安定な並べ替えという。 いうまでもなく、並べ替えが高速で終了し、しかも安定であるような並べ替えアルゴリズムの採用が望ましい。

データの並べ替えは最も基本的な計算処理の一部をなしている。 しかも取り扱うデータサーズは巨大化しており、並べ替えの効率化は計算時間の短縮に大きな影響を及ぼす。 このため、現在でも並べ替えのアルゴリズムと実装はいまも研究され続けている。 並べ替えを研究するための決定版は、毎度ながらKnuthの次の本だ。

最近では、 Tim Petersによって開発された実世界データの並べ換えを実行するためのマージ法と挿入法を組み合わせたハイブリッドで安定な並べ替え法であるTimsort（詳しい解説論文 Merge Strategies: from Merge Sort to TimSort）が、Python、Java SE,Androidの標準アルゴリズムとして採用されている。 条件さえ整えばより高速なquick法では最悪計算量が$\mathcal{O}(n^2)$となってしまう。 Timsortは安定でしかも最悪計算量が$\mathcal{O}(n\log n)$であるために、実用上の利点があるとされている。

以下、代表的な並べ替えアルゴリズムを数からなるリスト items を引数とする関数として与える。

バブルソート

def bubbleSort(items):
    for i in xrange(len(items)):
        for j in range(len(items)-1-i):
            if items[j] > items[j+1]:
                temp = items[j]
                items[j] = items[j+1]
                items[j+1] = temp

選択ソート

def selectionSort(items):
    for i in xrange(len(items)):
        min_pos = i
        for j in xrange(i + 1, len(items)):
            if items[j] < items[min_pos]:
                min_pos = j
        temp = items[min_pos]
        items[min_pos] = items[i]
        items[i] = temp

挿入ソート

    for i in range(1, len(items)):
        position = i
        current = items[i]
        while position > 0 and items[position-1] > current:
            items[position] = items[position-1]
            position -= 1
        items[position] = current

Shellソート

def ShellSort(items):
    gap = 1
    while gap < len(items):
        gap = 3 * gap + 1 # 1, 4, 13, 40, 121, 364, 1093,
    while gap > 0:
        for i in xrange(gap, len(items)):
            tmp = items[i]
            j = i - gap
            while j >= 0 and items[j] > tmp:
                items[j + gap] = items[j]
                j -= gap
            items[j + gap] = tmp
        gap /= 3

ヒープソート

次のヒープソートの関数 heapSort では、その内で関数 downheap を定義して、それを使っている。 

def heapSort(items):
    def downheap(list, left, right):
        tmp = list[left]
        child = None
        parent = None

        parent = left
        while parent < (right + 1) / 2:
            cl = parent * 2 + 1
            cr = cl + 1
            if cr <= right and list[cr] > list[cl]:
                child = cr
            else:
                child = cl
            if tmp >= list[child]:
                break
            list[parent] = list[child]
            parent = child
        list[parent] = tmp

    for i in xrange((len(items) - 1) / 2, -1, -1):
        downheap(items, i, len(items) - 1)
    for i in xrange(len(items) - 1, 0, -1):
        items[0], items[i] = items[i], items[0]
        downheap(items, 0, i - 1)

マージソート

次のマージソートの関数 mergeSort では、その内で関数 merge_sort を定義して、それを使っている。 

def mergeSort(items):
#Sort the elements of list items using the merge-sort algorithm
    def merge(S1, S2, items):
    #Merge two sorted lists S1(with length n1) and S2(with length n1) into sorted items
        i=j=0
        while i + j < len(items):
            if j == len(S2) or (i < len(S1) and S1[i] < S2[j]):
                items[i+j] = S1[i] # copy ith element of S1 as next item of items
                i += 1
            else:
                items[i+j] = S2[j] # copy jth element of S2 as next item of items
                j += 1

    n = len(items)
    if n < 2:
        return# list is already sorted
    # divide
    mid = n // 2
    S1 = items[0:mid]# copy of first half with length n1
    S2 = items[mid:n]# copy of second half with length n2
    # conquer (with recursion)
    mergeSort(S1)# sort copy of first half
    mergeSort(S2)# sort copy of second half
    # merge two sorted lists S1 and S2 into sorted list item
    merge(S1, S2, items)

与えられたリストを半分ずつに（下に向かって）わける 

            [85 24 63 45 17 31 96 50]

      [85 24 63 45]      +     [17 31 96 50]
    
  [85 24]   +   [63 45]       [17 31]   +   [96 50]

[85] + [24]   [63] + [45]   [17] + [31]   [96] + [50]

分けられた２つずつのリストを整列させながら（上に向かって）マージする 

             [17 24 31 45 50 63 85 96]
   
     [24 45 63 85]       +        [17 31 50 96]

  [24 85]   +  [45 63]        [17 31]   +  [50 96]

[85] + [24]   [63] + [45]   [17] + [31]   [96] + [50]

mergeソートのアルゴリズム解析

サイズ $n$ のリストのmergeソートの時間計算量は $\mathcal{O}(n\log n)$ である。

リスト items を並べ替える関数 mergeSort(items) は、ソートされた S1 と S2 をソートされるように items に併合するサブルーティン関数 merge(S1, S2, items) をコールする。

並べ替えの対象となるリスト item の長さ $n$ を2の整数商の長さ $\lceil n/2 \rceil$ と $n-\lceil n/2 \rceil $のリストにし、さらにそれぞれの半分にして‥と、リスト長さが1になるまで次々に2で割ち続ける回数（merge-tree $T$ の高さ）は $\lceil\log n \rceil$ である（$\lceil\log x \rceil$ は $x$ の天井関数）。 $T$ における深さ $i$ のmerge-treeのノード数は $2^i$ 個。

merge 関数 の計算量： len(S1)$=n_1$, len(S2)$=n_2$ としたとき、while loop内の各行を実行する時間は $\mathcal{O}(1)$ で、loopを1回実行するごとに、S1またはS2の要素がSに整列して並べられていく。 loopの回数は $n_1+n_2$で計算時間は $\mathcal{O}(n_1+n_2)$.

$T$の深さ $i$ におけるノードは$2^i$個ある。それぞれのノードの長さは $n/2^i$ であるので、再帰的に呼び出されるmergeに必要な時間は $\mathcal{O}(n/2^i$)$ である。 ノードごとにこの計算時間を要し、つまり、$T$の深さ $i$ に費やされる時間は $\mathcal{O}(2^i\codt n/2^i$)$ である（merge-tree $T$の深さによらず $\mathcal{O}(n)$ 時間必要）。 つまり、$T$ の高さが $\lceil n/2 \rceil$ であることから、$T$の$\lceil \log n \rceil +1$個の各段階ごとに $\mathcal{O}(n)$ 時間がかかる。

以上の観察は、以下のようにまとめることができる。 サイズ $n$ のリスト item をマージソートする関数 mergeSort(items) では、サイズが半分 $n/2 $ のリストについて mergeSort を2回呼び出し、サイズ $n/2+n/2$ へのマージ関数 merge（計算量は $n$ ｍの定数倍 $\mathcal{O}(n)$） を呼んでいる。 サイズ $n$ のmergeソートの計算量を $t(n)$ とすると（簡単のために $n$ は2ベキとする）、関数 mergeSort(items)の計算量は次の関係を満たしていることになる。 \[ t(n)= \begin{cases} a & \text{if $n\leqq 1$}\\ 2 t(n/2) + bn &\text{otherwise} \end{cases} \]

この再帰関係式は閉じていて、解くことができる。 \begin{align*} t(n) &= 2\big(2t(n/2^2) + (bn/2)\big) + bn\\ &= 2^2t(n/2^2) + 2(bn/2) +bn=2^2t(n/2^2) + 2bn & ldots\\ &= 2^it(n/2^i) +ibn \end{align*}

$2^i=n$ つまり $i=\log n$ に対しては、 $t(n)=a, n\leqq 1$ に注意すると \begin{align*} t(n) &= 2^{\log n}t(n/2^{\log n}) +(\log n)bn\\ &= nT(1) + bn\log n\\ &= an +bn\log n\\ &\sim \mathcal{O}(n\log n) \end{align*}

クイックソート

次のマージソートの関数 quickSort では、その内で関数 quick_sort を定義して、それを使っている。 

def quickSort(items):
    def quick_sort(list, left, right):
        pl = left
        pr = right
        y = list[(pl + pr) / 2]
        while True:
            while list[pl] < y: pl += 1
            while list[pr] > y: pr -= 1
            if pl <= pr:
                list[pl], list[pr] = list[pr], list[pl]
                pl += 1
                pr -= 1
            if pl > pr:
                break
        if left < pr: quick_sort(list, left, pr)
        if pl < right: quick_sort(list, pl, right)

    quick_sort(items, 0, len(items) - 1)

Python組み込みのソート

Pythonでは、リストの並べ替えメソッドのアルゴリズムにTimsortが使われている。 上記の関数に仕様に合わせて、これを pythonListSort と関数化しておきう。 

def pythonListSort(item):
    item.sort()

並べ替えの計算量比較

並べ替えアルゴリズムの時間計算量は、比較回数および入れ替え回数に直目して行う。 以下はデータサイズ $n$ に対する計算量。 ただし、さまざまに工夫されて改良が進んでいるので、以下はあくまでも教科書的な評価である。

並べ替えの計算量評価
アルゴリズム安定性平均時間最悪時間最良時間最悪空間量
バブル安定$\mathcal{O}(n^2)$$\mathcal{O}(n^2)$$\mathcal{O}(n)$$\mathcal{O}(1)$
選択不安定$\mathcal{O}(n^2)$$\mathcal{O}(n^2)$$\mathcal{O}(n)$$\mathcal{O}(n)$
挿入安定$\mathcal{O}(n^2)$$\mathcal{O}(n^2)$$\mathcal{O}(n)$$\mathcal{O}(n)$
Shell不安定Gap列の選択に依存
$\mathcal{O}(n^{3/2})\sim\mathcal{O}(n^{1.25})$		$\mathcal{O}(n^2)$$\mathcal{O}(n\log n)$$\mathcal{O}(n)$
ヒープ不安定$\mathcal{O}(n\log n)$$\mathcal{O}(n\log n)$$\mathcal{O}(n\log n)$$\mathcal{O}(1)$
マージ安定$\mathcal{O}(n\log n)$$\mathcal{O}(n\log n)$$\mathcal{O}(n\log n)$$\mathcal{O}(n)$
クイック不安定$\mathcal{O}(n\log n)$$\mathcal{O}(n^2)$$\mathcal{O}(n)$$\mathcal{O}(n)$
Tim(python)安定$\mathcal{O}(n\log n)$$\mathcal{O}(n\log n)$$\mathcal{O}(n)$$\mathcal{O}(n)$

　実際の並べ替え速度を比較する

これらの並べ替えに要する計算時間を実際に測定してみよう。 次の関数 stopwatch は第一引数に関数を、第二引数に関数引数をセットして、その実行時間単位をミリ秒[ms]で表示する。 時間の取得のために、2行目でパッケージ time をインポートしている。 

def stopwatch(function, arg = None):
    from time import clock
    start = clock()
    if arg is not None:
        function(arg)
    else:
        function()
    end = clock()
    print end - start

0から size_of_data -1 までの整数リスト data を与えて、これを shuffle(data) でシャッフルする。そのためにパッケージ random をインポートしておく。 こうしてシャッフルされた長さ size_of_data の data を比較する並べ替え関数の数（8個ある）だけ a, b, c, d, e, f, g, h に代入する。

この準備の後に、次のようにして同じシャッフルデータを使って並べ替える時間を測定しよう。 例えば、次のようにしてみる。 

# 各種並べ替え関数が定義されている

from random import shuffle

size_of_data = 1000
data = range(size_of_data)
shuffle(data)

a = data
b = data
c = data
d = data
e = data
f = data
g = data
h = data

sdata = [a, b, c, d, e, f, g, h]
sorter = [bubbleSort, selectionSort, insertionSort, \
        ShellSort, heapSort, mergeSort, quickSort, pythonListSort]

for i, s in enumerate(sorter):
    print '[%15s]' % s.__name__,
    stopwatch(s, sdata[i])

size_of_data を 10000 として実行した結果は以下のようである。 

$ ./sorting_compare.py
[     bubbleSort] 5.603415
[  selectionSort] 2.061298
[  insertionSort] 0.001251
[      ShellSort] 0.009308
[       heapSort] 0.035181
[      mergeSort] 0.022184
[      quickSort] 0.007951
[ pythonListSort] 0.000147

演習： 上で定義した8種の並べ替えアルゴリズムの実行時間を測定するスクリプト sort_records.py を実行してみなさい。 データサイズ size_of_data を小さくしたり大きくしたりして検証しなさい。