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の場合こういう入れ替えが可能なのでこちらにしました。
次回はヒープソートの予定です。