Goでのアルゴリズムクイックリファレンス第2版(4.3 分割ベースのソート)

Goに慣れるためとアルゴリズムの復習の為に週1ぐらいで更新していきます。アルゴリズムクイックリファレンス 第2版を読んで各種アルゴリズムをGoで実装して行きます。

前回: Goでのアルゴリズムクイックリファレンス第2版(4.2 選択ソート)

今回はヒープソートです。

• リストの並べ替えを二分ヒープ木を用いて行うソートのアルゴリズム
• 計算量は O(n log n)
• 安定ソートではない
• アルゴリズム
  • 未整列のリストから要素を取り出し、順にヒープに追加する。すべての要素を追加するまで繰り返し。
  • ルート（最大値または最小値)を取り出し、整列済みリストに追加する。すべての要素を取り出すまで繰り返し。

package main

import (
    "fmt"
    "math/rand"
)

func sort(a *[]int) {
    buildHeap(a)
    n := len(*a)
    for i := n - 1; i >= 0; i-- {
        (*a)[0], (*a)[i] = (*a)[i], (*a)[0]
        heapify(a, 0, i)
    }
}

func buildHeap(a *[]int) {
    n := len(*a)
    for i := n/2 - 1; i >= 0; i-- {
        heapify(a, i, n)
    }
}

func heapify(a *[]int, idx int, max int) {
    largest := idx
    left := 2*idx + 1
    right := 2*idx + 2

    if left < max && (*a)[left] > (*a)[idx] {
        largest = left
    }

    if right < max && (*a)[right] > (*a)[largest] {
        largest = right
    }

    if largest != idx {
        (*a)[idx], (*a)[largest] = (*a)[largest], (*a)[idx]
        heapify(a, largest, max)
    }
}

func main() {
    var ary []int
    size := 30
    for i := 0; i < size; i++ {
        ary = append(ary, rand.Intn(size-1))
    }
    fmt.Println(ary)
    sort(&ary)
    fmt.Println(ary)
}

次回はクイックソートの予定です。