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

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

今回は選択ソートです。

整列アルゴリズムの一種
平均,最良、最悪と全部(O(n2))と遅い処理。
安定してない
アルゴリズム
- 範囲Aから最大値を選択して、右端の要素A[n-1]と交換
- これをより範囲の狭いA[0,n-1]に繰り返してAを整列させる

package main

import (
	"fmt"
	"math/rand"
)

func selectMax(ar *[]int, left int, right int) int {
	maxPos, i := left, left
	for i <= right {
		if (*ar)[i] > (*ar)[maxPos] {
			maxPos = i
		}
		i++
	}

	return maxPos
}

func sortPointers(ar *[]int, n int) {
	for i := n - 1; i >= 1; i-- {
		maxPos := selectMax(ar, 0, i)
		if maxPos != i {
			(*ar)[i], (*ar)[maxPos] = (*ar)[maxPos], (*ar)[i]
		}
	}
}


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

今回の書き方で迷ったのは、

(*ar)[i], (*ar)[maxPos] = (*ar)[maxPos], (*ar)[i]

の部分で、ここは、伝統的な書き方だとこういう書き方になるんですが

tmp := (*ar)[i]
(*ar)[i] = (*ar)[maxPos]
(*ar)[maxPos] = tmp

Goの場合こういう入れ替えが可能なのでこちらにしました。

次回はヒープソートの予定です。