pythonでヒープソートを実装してみた

の続き？です。

前段でヒープを作りました。

ヒープソートはヒープの頂点から値を取り出す→ヒープを再構築する→ヒープの頂点から値を…

と繰り返すことでソートを行う…

という処理をヒープソートと呼ぶらしいです。

heap_sort.py

import random
import copy

# 準備する値の数を入力
numbers = 10000

sorted_list = []

# 乱数の作成
num_list = list(range(numbers))
random.shuffle(num_list)

def heap(num_list):
    
    while True:
        # whileループ開始時の配列を保持
        check_list = copy.deepcopy(num_list)
        # 頂点から順にチェックしていく
        for i in range(len(num_list)):
            # ノードの下に値が1つしか残っていない場合(終端パターンその1)
            if len(num_list) == (i+1)*2:
                node = num_list[i]
                left = num_list[(i+1)*2-1]
                # ノードより子供が大きい場合は値を入れ替える
                if node > left:
                    num_list[i] = left
                    num_list[(i+1)*2-1] = node
                    # 値の入れ替えが発生したので上から再確認
                    break
                # 終端なのでbreak
                break
            
            elif len(num_list) > (i+1)*2:
            # ノードの下に値が2つ以上残っていない場合(終端ではないパターン)
                node = num_list[i]
                left = num_list[(i+1)*2-1]
                right = num_list[(i+1)*2]
                # ノードより子供のいずれかが大きい場合、より値の小さい子供と値を入れ替える
                if node > left or node > right:
                    if left < right:
                        num_list[i] = left
                        num_list[(i+1)*2-1] = node
                    else:
                        num_list[i] = right
                        num_list[(i+1)*2] = node
                    # 値の入れ替えが発生したので上から再確認
                    break
            else:
            # ノードの下に値が残っていない場合(終端パターンその2)
                break
        # whileループの冒頭と比較して、配列が同一だった場合whileループをbreak
        if check_list == num_list:
            break
    return num_list



def main(num_list):
    # メイン処理
    print("START : ",num_list)

    while len(num_list) != 0:
        num_list = heap(num_list)
        sorted_list.append(num_list.pop(0))
    print("GOAL  : ",sorted_list)

if __name__ == '__main__':
    main(num_list)