ソート詰め合わせパック

sort.py

# -*- encoding: utf-8 -*-
# ソート詰め合わせパック
#     * バブルソート（単純交換ソート）
#     * 単純選択ソート
#     * シャトルソート（単純挿入ソート）
#     * シェルソート
#     * クイックソート
#     * ヒープソート
# Copyright 2015 daiz. All Rights Reserved.

def printd(data):
    '''配列データをカンマ区切りで表示する'''
    print ("{}".format(data))[1:-1]

def bubble(data, length):
    '''バブルソート（単純交換ソート）
    配列の後ろから要素を見てゆき、隣り合う要素を比較し、必要ならば交換する。
    '''
    for i in range(0, length-1):
        for j in range(length-1, i, -1):
            if(data[j-1] > data[j]):
                # swap
                (data[j], data[j-1]) = data[j-1], data[j]
    return data

def selection(data, length):
    '''単純選択ソート
    (a) 未ソート部から最小のキーをもつ要素data[min]を選択する。
    (b) a[min]と未ソート部の先頭の要素を比較する。必要ならば交換する。
    '''
    for i in range(0, length-1):
        min = i
        for j in range(i+1, length):
            if(data[j] < data[min]): min = j
        # swap
        (data[i], data[min]) = data[min], data[i]
    return data

def shuttle(data, length):
    '''シャトルソート（単純挿入ソート）
    『原列の先頭要素を目的列の＜適当な位置＞に挿入する』操作を繰り返す。
    人間がトランプを並べ替える際に行う方法によく似たアルゴリズムである。
    '''
    for i in range(1, length):
        tmp = data[i]
        j = i
        # 繰り返しを続行する条件
        # (a) 目的列の左端に達した。　
        # --> j が 0 より大きい。
        # (b) tmpと等しいか小さいキーを持った項目data[j]が見つかった。
        # --> a[j-1] の値が tmp よりも大きい。
        while((j > 0 and data[j-1] > tmp) is True):
            data[j] = data[j-1]
            j -= 1
        data[j] = tmp
    return data

def shell(data, length):
    '''シェルソート
    最初はなるべく離れた要素をグループ化して、おおまかなソートを行い、
    そのグループを縮めることによって交換回数を減らそうというアイデアである。
    いずれのソートも、すべて単純挿入ソートによって行う。
    '''
    h = length/2
    while(h > 0):
        for i in range(h, length):
            tmp = data[i]
            j = i - h
            while((j >= 0 and data[j] > tmp) is True):
                data[j+h] = data[j]
                j -= h
            data[j+h] = tmp
        h /= 2
    return data

def quick(data, l_index, r_index):
    '''クイックソート
    枢軸（ピボット）よりも大きか否かでグループ分けをし、それぞれのグループ内で
    再び同様の操作を行う。グループの要素数が1になった時点でソート完了。
    '''
    cl = l_index    # 左カーソル
    cr = r_index    # 右カーソル
    x = data[(cl+cr)/2]    # ピボットとして中央に位置する値を採用

    while(cl <= cr):
        # ピボットよりも左側の要素の中で、
        # ピボットよりも大きい要素を見つけるまで走査する。
        while(data[cl] < x): cl += 1
        # ピボットよりも左側の要素の中で、
        # ピボットよりも小さい要素を見つけるまで走査する。
        while(data[cr] > x): cr -= 1
        # カーソルが交差していない（clがcrより左に位置する）ことを確かめて
        # 要素をswapする
        if(cl <= cr):
            # swap
            (data[cl], data[cr]) = data[cr], data[cl]
            # 再び走査を再開する
            cl += 1
            cr -= 1

    # ここで、この回のグループ分けが完了している状態
    # 分割によって作られたグループの要素数が1でない場合、さらに分割する
    if(l_index < cr): quick(data, l_index, cr)
    if(cl < r_index): quick(data, cl, r_index)

    return data


def pushdown(data, root, bottom):
    i = root
    j = bottom
    # data[i] ～ data[j] をヒープ化
    # data[i] を、 data[i+1] から data[j] のヒープに押し込む
    '''ヒープへ要素を追加する（上から下へ押し込む）
    配列の i+1 番目から j 番目までの要素がヒープ条件を満たしているとき、
    i 番目の要素を追加する手順
    (z) 2つの子 data[2i+1] と data[2i+2] のうち大きい方を取得する
    (a) 子が自分以下なら終了
    (b) 子が自分より大きいときは、2つの子 data[2i+1] と data[2i+2] のうち
        大きい方と交換する
    (c) 交換によってヒープ条件が崩れる可能性があるので、
        交換した先に移動して (a) から再調整する
    '''
    ch = 2*i + 1    # 子（child）の位置（左）

    while(ch <= j):
        if(ch < j and data[ch] < data[ch+1]): ch += 1    # (z)
        # この時点で ch は、左右の子のうち、大きい方の位置を保持している
        if(data[ch] < data[i]): break    # (a)
        (data[ch], data[i]) = data[i], data[ch]    # (b); swap
        # i をその子の位置へ
        i = ch
        # ch を更にその子（左側の子）の位置へ
        ch = 2*i + 1    # (c)

    return data


def heap(data, length):
    # ヒープ条件: 子が自分以下であること
    '''ヒープソート
    ヒープを用いてソートするアルゴリズム。
    ヒープの根から値を取り出すと、最大値が得られる。このことを利用した、
    選択ソートの応用的なアルゴリズム。
    data[i] の子は data[2i+1], data[2i+2]
    '''
    # 配列のヒープ化
    # 子を持っているのは (n-1)/2以下にある要素であることに注目
    i = (length - 1) / 2
    while(i >= 0):
        data = pushdown(data, i, length-1)
        i -= 1
        
    '''根を取り出して末尾へ移動（後ろの要素からそれより右のヒープに押し込む）
    (a) i の値を n-1 で初期化する
    (b) data[0] と data[i] を交換する
    (c) data[0], data[1], ..., data[i-1] を再ヒープ化する
    (d) i をデクリメントして0になれば終了する。そうでなければ(b)に戻る
    '''
    i = length - 1
    while(i > 0):
        # swap
        # data[0] と data[i] を交換。
        # data[i] に data[0] から data[i] までの最大値が入る。
        (data[0], data[i]) = data[i], data[0]
        data = pushdown(data, 0, i-1)
        i -= 1

    return data

if __name__ == '__main__':
    input_data = [22, 5, 11, 32, 120, 68, 70, 3, -1]
    length = len(input_data);
    # バブルソート
    printd(bubble(input_data, length))
    # 単純選択ソート
    printd(selection(input_data, length))
    # シャトルソート
    printd(shuttle(input_data, length))
    # シェルソート
    printd(shell(input_data, length))
    # クイックソート
    printd(quick(input_data, 0, length-1))
    # ヒープソート
    printd(heap(input_data, length))


# 参考書籍
# 『明解 C言語によるアルゴリズムとデータ構造』
# 柴田望洋, 辻亮介 著
# Softbank Creative