Python

Pythonで学ぶアルゴリズム ソート ヒープソート

  /

ヒープソートを実装してみます。

概要

ヒープソート (heap sort) とはリストの並べ替えを二分ヒープ木を用いて行うソートのアルゴリズムである[ 2 ]（ヒープ領域とは無関係であることに注意する）。

アルゴリズムは、以下のように2つの段階から構成される。

1. 未整列のリストから要素を取り出し、順にヒープに追加する。すべての要素を追加するまで繰り返し。

2. ルート（最大値または最小値)を取り出し、整列済みリストに追加する。すべての要素を取り出すまで繰り返し。

計算量は O(n log n) となる[ 2 ]。安定ソートではない[ 2 ]。

ヒープソート – Wikipedia

サンプルコード

import random


data_len = 10
data = random.sample(range(1, 42), data_len)
print(data)


def heapify(unsorted, index, heap_size):
    largest = index
    left_index = 2 * index + 1
    right_index = 2 * index + 2
    if left_index < heap_size and unsorted[left_index] > unsorted[largest]:
        largest = left_index

    if right_index < heap_size and unsorted[right_index] > unsorted[largest]:
        largest = right_index

    if largest != index:
        unsorted[largest], unsorted[index] = unsorted[index], unsorted[largest]
        heapify(unsorted, largest, heap_size)


def heap_sort(unsorted):

    n = len(unsorted)
    for i in range(n // 2 - 1, -1, -1):
        heapify(unsorted, i, n)
        print(unsorted)
    for i in range(n - 1, 0, -1):
        unsorted[0], unsorted[i] = unsorted[i], unsorted[0]
        heapify(unsorted, 0, i)
        print(unsorted)
    return unsorted


heap_sort(data)

実行結果（例）

[22, 41, 3, 35, 32, 25, 37, 17, 29, 6]
[22, 41, 3, 35, 32, 25, 37, 17, 29, 6]
[22, 41, 3, 35, 32, 25, 37, 17, 29, 6]
[22, 41, 37, 35, 32, 25, 3, 17, 29, 6]
[22, 41, 37, 35, 32, 25, 3, 17, 29, 6]
[41, 35, 37, 29, 32, 25, 3, 17, 22, 6]
[37, 35, 25, 29, 32, 6, 3, 17, 22, 41]
[35, 32, 25, 29, 22, 6, 3, 17, 37, 41]
[32, 29, 25, 17, 22, 6, 3, 35, 37, 41]
[29, 22, 25, 17, 3, 6, 32, 35, 37, 41]
[25, 22, 6, 17, 3, 29, 32, 35, 37, 41]
[22, 17, 6, 3, 25, 29, 32, 35, 37, 41]
[17, 3, 6, 22, 25, 29, 32, 35, 37, 41]
[6, 3, 17, 22, 25, 29, 32, 35, 37, 41]
[3, 6, 17, 22, 25, 29, 32, 35, 37, 41]
RELATED POST