いろんなアルゴリズム"00.00.00.06"

立ち位置・仕様

• いろんなアルゴリズムをコピペできるように記録するのみ
• 最適化が目的でない
• たまにメモとして解説を残す
• 最低限でまとめる
• データを抽出しやすいように個別のIDを付与
• あるアルゴリズムにおいて、他のアルゴリズムが登場する際にはそのIDを付与
• IDは16進数表記
• なるべく最低限なパッケージで実装
• なるべく特殊なオブジェクト型は使用しない

TargetID

00.00.00.06

ReferenceID

ヒープソート

def heapSort(l):
    n = len(l)
    for i in range(n//2-1, -1, -1):
        heapify(l, i, n)

    for i in range(n-1, 0, -1):
        l[0], l[i] = l[i], l[0]
        heapify(l, 0, i)
        
    return l

def heapify(l, i, heap_size):
    largest = i
    left = 2 * i + 1
    right = 2 * i + 2

    if left < heap_size and l[left] > l[largest]:
        largest = left

    if right < heap_size and l[right] > l[largest]:
        largest = right

    if largest != i:
        l[largest], l[i] = l[i], l[largest]
        heapify(l, largest, heap_size)

使用方法

l = [5,2,3,6,2,1]
l = heapSort(l):
print(l) # [1, 2, 2, 3, 5, 6]