Pythonで実装するソートアルゴリズム – ヒープソート編 –

こんばんは。今日は、ソートアルゴリズムについて学んだことを整理しておきたいと思います。

最近はReact Native, Azureの話が多かったのですが、今日はもう少し理論的なお話になります。

それではまいります。

ヒープソートの概要

• 1964年にJ.W.J. Williamsによって発明されたソートアルゴリズム
• 選択ソートの１種
• 安定ソートではない（同じ値の場合の順番維持は保証されない）
• n個のデータをソートする際の最良計算量および平均計算量はnlognのオーダー（底は2、だそう）
• 最悪の計算量もnlogn
• ヒープソートの性能は安定しており、クイックソートなどと比べてもデータの出現順序による計算量の変化は小さい。ただし、平均的にはクイックソートよりも遅くなるといわれている。
• 処理を並列化できない、空間的局所性が低い（メモリへのアクセスが連続しておらず、ランダムアクセスになる）など、現代の高速化技法に適さない特徴もある。

ヒープソートの手順

1. 未整列のリストから要素を取り出し、順にヒープに追加する。これをすべての要素を追加するまで繰り返す。
2. ルート（最大値または最小値）を取り出し、整列済リストに追加する。これをすべての要素を取り出すまで繰り返す。

以下のサイトで、ヒープソートの課程を分かりやすく解説されていました。

https://medium-company.com/%E3%83%92%E3%83%BC%E3%83%97%E3%82%BD%E3%83%BC%E3%83%88/

ヒープソートの実装

当然ながら、こうしたソートアルゴリズムに対してはライブラリが用意されており、実用の際には都度一から実装する必要はありません。

これにはnumpyのsort関数が使えます。

https://numpy.org/doc/stable/reference/generated/numpy.sort.html

コード

import random

a = []

for i in range(10):
    x = random.randint(1,100)
    a.append(x)

np.sort(a, kind='heap')

#実行結果
array([30, 32, 35, 38, 44, 60, 61, 63, 67, 71])

ちなみに、実行時間を計測してみると、配列要素数5000程度まではまったく時間がかからず、5000を超えると指数的に時間が増えていっていくことが分かります。1000万要素数で10秒程度なので、2秒程度だったクイックソートと比べるとやはりやや低速のようです。（理論の通り）

が、これでは理解も深まらないので、手動でも実装してみたいと思います。実装は、 記載のサイトのコードを利用させていただきました。

コードは以下の通りになります。

def heap_sort(array):
    i = 0
    n = len(array)

    while(i < n):
        # ヒープを構成
        upheap(array, i)
        i += 1

    while(i > 1):
        # ヒープから最大値を取り出し
        i -= 1
        tmp = array[0]
        array[0] = array[i]
        array[i] = tmp

        # ヒープの再構成
        downheap(array, i-1)

# array[n]をヒープ構成部(0～n-1)の最適な位置へ移動
def upheap(array, n):
    while n != 0:
        parent = int((n - 1) / 2)
        if array[n] > array[parent]:
            # 親より大きな値の場合親子の値を交換
            tmp = array[n]
            array[n] = array[parent]
            array[parent] = tmp
            n = parent
        else:
            break

# ルート[0]をヒープ(0～n)の最適な位置へ移動
def downheap(array, n):
    if n == 0: return
    parent = 0
    while True:
        child = 2 * parent + 1 # array[n]の子要素
        if child > n: break
        if (child < n) and array[child] < array[child + 1]:
            child += 1
        if array[parent] < array[child]: # 子要素より小さい場合スワップ
            tmp = array[child]
            array[child] = array[parent]
            array[parent] = tmp
            parent = child; # 交換後のインデックスを保持
        else:
            break

# デバッグ
if __name__ == "__main__":
    array = [1,2,3,4,5,3,2,1,4,3,4,5,0]
    print("before", array)
    heap_sort(array)
    print("after ", array)

before [1, 2, 3, 4, 5, 3, 2, 1, 4, 3, 4, 5, 0]
after  [0, 1, 1, 2, 2, 3, 3, 3, 4, 4, 4, 5, 5]

参考文献

今回大変参考にさせていただいた記事をここにまとめておきます。

https://ja.wikipedia.org/wiki/%E3%83%92%E3%83%BC%E3%83%97%E3%82%BD%E3%83%BC%E3%83%88