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)
}

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