「Pythonではじめるアルゴリズム入門」#03 - ソートアルゴリズム

「Pythonではじめるアルゴリズム入門」の学習記録です。学習に使ったファイルやコードなどをアップしていきます。
今回はソートに用いるアルゴリズムについて学びました。

ソートに用いるアルゴリズム

リストを昇順・降順に並べ替える際の手法・計算量について考えます。

• 選択ソート
• 挿入ソート
• バブルソート
• ヒープソート
• マージソート
• クイックソート

選択ソート

リストの中から最小の値を見つけ、値をリストの先頭と交換します。計算量のオーダーはO(n^2)です。

#先頭のインデックスから調べていき、徐々に後ろの方に範囲を狭める
#実際に何回処理が行われたかをいカウントする

data = [6,15,4,2,8,5,11,9,7,13]
calcurated = 0
print("ソート前：")
print(data)

for i in range(len(data)):
    min = i
    for j in range(i+1, len(data)):
        if data[min] > data[j]:
            min = j
            calcurated += 1

    data[i],data[min] = data[min], data[i]

print("ソート後：")
print(data)
print("処理回数：")
print(calcurated)

ソート前：
[6, 15, 4, 2, 8, 5, 11, 9, 7, 13]
ソート後：
[2, 4, 5, 6, 7, 8, 9, 11, 13, 15]
処理回数：
11

挿入ソート

データを先頭から順に比較し、格納する位置を見つけて追加します。値はリストの一番後ろにまず格納し、１つずつリストの後ろから順にコピーしていくという方法でソートします。計算量のオーダーはO(n^2)です。

#先頭のインデックスから調べていき、徐々に後ろの方に範囲を狭める
data = [6,15,4,2,8,5,11,9,7,13]
calcurated = 0
print("ソート前：")
print(data)

for i in range(1, len(data)):
    temp = data[i]
    j = i-1
    while (j>=0) and (data[j] > temp):
        data[j+1] = data[j]
        j-=1
        calcurated += 1

    data[j+1] = temp

print("ソート後：")
print(data)
print("処理回数：")
print(calcurated)

ソート前：
[6, 15, 4, 2, 8, 5, 11, 9, 7, 13]
ソート後：
[2, 4, 5, 6, 7, 8, 9, 11, 13, 15]
処理回数：
17

バブルソート

データが右側の方が小さければ左側と交換する、というタスクを繰り返します。最小の数が左端・最大の数が右端に行くまでタスクを繰り返すとソートが完了します。計算量のオーダーはO(n^2)です。

#先頭のインデックスから調べていき、徐々に後ろの方に範囲を狭める
data = [6,15,4,2,8,5,11,9,7,13]
calcurated = 0
print("ソート前：")
print(data)

for i in range(len(data)):
    #ソートが完了した数を引いた数を引いた分だけループする
    for j in range(len(data)-i-1):
        #右のデータの方が小さければ、左と交換する
        if data[j] > data[j+1]:
            data[j], data[j+1]= data[j+1], data[j]
            calcurated += 1

print("ソート後：")
print(data)
print("処理回数：")
print(calcurated)

ソート前：
[6, 15, 4, 2, 8, 5, 11, 9, 7, 13]
ソート後：
[2, 4, 5, 6, 7, 8, 9, 11, 13, 15]
処理回数：
17

ヒープソート

ヒープは木構造のデータ構造で、子ノードの値は親ノードと比べ等しいか大きくなる、という条件を満たす木構造データです。
ヒープに要素を追加する場合、木構造の最後の部分に要素を追加します。
ヒープを使って値をソートするには、追加した要素と親ノードを比較し親ノードの方が小さければそれと交換する、というタスクを繰り返します。
ヒープを使ったソートの計算数はO(n・logn)となります。これはn個のノードがある木の高さがlog2(n)であり、計算数が2の対数に比例する為です。選択ソートと比べると、データ量が多いときに処理能力が向上しますが、ヒープを作成する計算が必要となります。

data = [6,15,4,2,8,5,11,9,7,13]
calcurated = 0

print("データのリスト：")
print(data)

#ヒープ構造を構成する
for i in range(len(data)):
    j = i
    #子ノードが親ノードよりも小さいかを判定
    while (j>0) and (data[(j-1)//2] < data[j]):
        #あてはまる場合は、親ノードと交換する
        data[(j-1)//2] , data[j] = data[j], data[(j-1)//2]
        #交換が終わったら、親ノードの探索に移行する
        j = (j-1)//2

        calcurated +=1
print("ヒープ構造構成後：")
print(data)

#ヒープ構造になったリストをソートする
for i in range(len(data), 0, -1):
    #ヒープの先頭と交換
    data[i-1], data[0] = data[0], data[i-1]
    j = 0
    #親ノードの左下・右下の値の方が小さい場合
    while ((2*j+1 < i-1) and (data[j] < data[2*j+1])) or ((2*j+2 < i-1) and (data[j] < data[2*j+2])):
        #左下>右下の場合
        if(2*j+2 == i-1) or (data[2*j+1] > data[2*j+2]):
            #親ノードと交換
            data[j], data[2*j+1] = data[2*j+1], data[j]
            #探索するノードを左下に移動
            j = 2*j+1
            calcurated +=1
        #右下>左下の場合
        else:
            #親ノードと交換
            data[j], data[2*j+2] = data[2*j+2], data[j]
            #探索するノードを右下に移動
            j = 2*j+2
            calcurated +=1

#ソートを実行する
print("ソート後：")
print(data)
print("処理回数：")
print(calcurated)

データのリスト：
[6, 15, 4, 2, 8, 5, 11, 9, 7, 13]
ヒープ構造構成後：
[15, 13, 11, 8, 9, 4, 5, 2, 7, 6]
ソート後：
[2, 4, 5, 6, 7, 8, 9, 11, 13, 15]
処理回数：
18

マージソート

ソートしたいデータを2分割するタスクを繰り返し、これらがバラバラになった状態からソートを開始します。n個リストを分割した際の段数はlog2(n)となり、リストが結合されるまでの計算時間はヒープソートと同様O(n・logn)となります。

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

print("データのリスト：")
print(data)

#マージソートを実行する為の関数
def merge_sort(data):
    #データが1つしかない→値をそのまま返す
    if len(data) <= 1:
        return data
    #リストの中央のインデックスを計算
    mid = len(data)//2
    #データの右側
    left=merge_sort(data[:mid])
    #データの右側
    right=merge_sort(data[mid:])
    #データを結合する
    return merge(left, right)

#データ結合を実行するための関数
def merge(left, right):
    result = []
    i,j = 0,0

    while (i<len(left)) and (j<len(right)):
        #左<＝右の時 - 返り値に左側のリストから取り出して追加
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        #右<＝左の時 - 返り値に右側のリストから取り出して追加
        else:
            result.append(right[j])
            j += 1

    #残りをまとめて追加する
    if i < len(left):
        result.extend(left[i:])
    if j < len(right):
        result.extend(right[j:])
    return result

print("ソート後：")
print(merge_sort(data))

データのリスト：
[6, 15, 4, 2, 8, 5, 11, 9, 7, 13]
ソート後：
[2, 4, 5, 6, 7, 8, 9, 11, 13, 15]

クイックソート

リストからデータを1つ選び、小さい要素と大きい要素に分割します。
分割の基準となる値はピボット(Pivot)といいます。このタスクを再帰的に繰り返し、データ数が1になるまで繰り返します。

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

print("データのリスト：")
print(data)

#マージソートを実行する為の関数
def quick_sort(data):
    #データ数が1になるまで繰り返す
    if len(data) <= 1:
        return data

    #ピボットの値はデータの先頭とする
    pivot = data[0]
    left, right, same = [], [], 0

    for i in data:
        #値がピボットより小さい→左側のリストにアペンド
        if i < pivot:
            left.append(i)
        #値がピボットより大きい→右側のリストにアペンド
        elif i > pivot:
            right.append(i)
        else:
            same += 1
    #左側を再帰的にクイックソート
    left = quick_sort(left)
    #右側を再帰的にクイックソート
    right = quick_sort(right)

    #ソートされた値 + ピボットと一致した値
    return left + [pivot]*same + right

print("ソート後：")
print(quick_sort(data))

データのリスト：
[6, 15, 4, 2, 8, 5, 11, 9, 7, 13]
ソート後：
[2, 4, 5, 6, 7, 8, 9, 11, 13, 15]

Pythonのsortメソッド

ソートアルゴリズムは、たいていPythonのsortメソッドを使うと最も高速な処理を自動で行ってくれます。計算量をカウントする等でなければ、sortメソッドを使うと間違いないでしょう。

#sortメソッドでソートする
data = [6,15,4,2,8,5,11,9,7,13]
calcurated = 0
print("ソート前：")
print(data)

data.sort()

print("ソート後：")
print(data)

ソート前：
[6, 15, 4, 2, 8, 5, 11, 9, 7, 13]
ソート後：
[2, 4, 5, 6, 7, 8, 9, 11, 13, 15]

※（「Pythonではじめるアルゴリズム入門」より引用）