アルゴリズムの勉強とGoの勉強を兼ねて、アルゴリズム図鑑 絵で見てわかる26のアルゴリズム で紹介されているソートを実装してみました。
各ソートの仕組みは、検索するとわかりやすい解説が出てくるかと思います。
初めてGoを触ったので、書き方がGoっぽくない可能性大です。
自分向けの備忘用途がメインですが、参考程度に使ってもらえれば嬉しいです。
バルブソート
サンプルコード
main.go
package main
import (
"fmt"
)
func sort(nums []int) []int {
for i := 0; i < len(nums); i++ {
isSwapped := false
for j, value := range nums[:len(nums)-i-1] {
if value > nums[j+1] {
nums[j] = nums[j+1]
nums[j+1] = value
isSwapped = true
}
fmt.Println(nums)
}
if !isSwapped {
break
}
fmt.Println("-----")
}
return nums
}
func main() {
nums := []int{5, 9, 3, 1, 2, 8, 4, 7, 6}
fmt.Println(nums)
fmt.Println("-----BEGIN-----")
result := sort(nums)
fmt.Println("----- END -----")
fmt.Println(result)
}
出力結果
[5 9 3 1 2 8 4 7 6]
-----BEGIN-----
[5 9 3 1 2 8 4 7 6]
[5 3 9 1 2 8 4 7 6]
[5 3 1 9 2 8 4 7 6]
[5 3 1 2 9 8 4 7 6]
[5 3 1 2 8 9 4 7 6]
[5 3 1 2 8 4 9 7 6]
[5 3 1 2 8 4 7 9 6]
[5 3 1 2 8 4 7 6 9]
-----
[3 5 1 2 8 4 7 6 9]
[3 1 5 2 8 4 7 6 9]
[3 1 2 5 8 4 7 6 9]
[3 1 2 5 8 4 7 6 9]
[3 1 2 5 4 8 7 6 9]
[3 1 2 5 4 7 8 6 9]
[3 1 2 5 4 7 6 8 9]
-----
[1 3 2 5 4 7 6 8 9]
[1 2 3 5 4 7 6 8 9]
[1 2 3 5 4 7 6 8 9]
[1 2 3 4 5 7 6 8 9]
[1 2 3 4 5 7 6 8 9]
[1 2 3 4 5 6 7 8 9]
-----
[1 2 3 4 5 6 7 8 9]
[1 2 3 4 5 6 7 8 9]
[1 2 3 4 5 6 7 8 9]
[1 2 3 4 5 6 7 8 9]
[1 2 3 4 5 6 7 8 9]
----- END -----
[1 2 3 4 5 6 7 8 9]
選択ソート
サンプルコード
main.go
package main
import (
"fmt"
)
func sort(nums []int) []int {
for i, v1 := range nums {
minValueIndex := i
minValue := v1
for j, v2 := range nums[i:] {
if minValue > v2 {
minValueIndex = i + j
minValue = v2
}
}
nums[i] = minValue
nums[minValueIndex] = v1
fmt.Println(nums)
}
return nums
}
func main() {
nums := []int{5, 9, 3, 1, 2, 8, 4, 7, 6}
fmt.Println(nums)
fmt.Println("-----BEGIN-----")
result := sort(nums)
fmt.Println("----- END -----")
fmt.Println(result)
}
出力結果
[5 9 3 1 2 8 4 7 6]
-----BEGIN-----
[1 9 3 5 2 8 4 7 6]
[1 2 3 5 9 8 4 7 6]
[1 2 3 5 9 8 4 7 6]
[1 2 3 4 9 8 5 7 6]
[1 2 3 4 5 8 9 7 6]
[1 2 3 4 5 6 9 7 8]
[1 2 3 4 5 6 7 9 8]
[1 2 3 4 5 6 7 8 9]
[1 2 3 4 5 6 7 8 9]
----- END -----
[1 2 3 4 5 6 7 8 9]
挿入ソート
サンプルコード
main.go
package main
import (
"fmt"
)
func sort(nums []int) []int {
result := nums[0:1]
fmt.Println(result, nums[1:])
for i, value := range nums[1:] {
for j, sortedValue := range result {
if value < sortedValue {
result = append(result[:j], append([]int{value}, result[j:]...)...)
break
}
if j == len(result)-1 {
result = append(result, value)
break
}
}
fmt.Println(result, nums[i+2:])
}
return result
}
func main() {
nums := []int{5, 9, 3, 1, 2, 8, 4, 7, 6}
fmt.Println(nums)
fmt.Println("-----BEGIN-----")
result := sort(nums)
fmt.Println("----- END -----")
fmt.Println(result)
}
出力結果
[5 9 3 1 2 8 4 7 6]
-----BEGIN-----
[5] [9 3 1 2 8 4 7 6]
[5 9] [3 1 2 8 4 7 6]
[3 5 9] [1 2 8 4 7 6]
[1 3 5 9] [2 8 4 7 6]
[1 2 3 5 9] [8 4 7 6]
[1 2 3 5 8 9] [4 7 6]
[1 2 3 4 5 8 9] [7 6]
[1 2 3 4 5 7 8 9] [6]
[1 2 3 4 5 6 7 8 9] []
----- END -----
[1 2 3 4 5 6 7 8 9]
ヒープソート
ヒープを実装する元気はなかったので、既存のパッケージを使いました。
heap - The Go Programming Language
サンプルコード
main.go
package main
import (
"container/heap"
"fmt"
)
// An IntHeap is a min-heap of ints.
type IntHeap []int
func (h IntHeap) Len() int { return len(h) }
func (h IntHeap) Less(i, j int) bool { return h[i] < h[j] }
func (h IntHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *IntHeap) Push(x interface{}) {
// Push and Pop use pointer receivers because they modify the slice's length,
// not just its contents.
*h = append(*h, x.(int))
}
func (h *IntHeap) Pop() interface{} {
old := *h
n := len(old)
x := old[n-1]
*h = old[0 : n-1]
return x
}
func sort(nums []int) []int {
h := &IntHeap{}
heap.Init(h)
for i:=0; i <len(nums); i++ {
heap.Push(h, nums[i])
}
var result []int
for h.Len() > 0 {
value := heap.Pop(h)
result = append(result, value.(int))
fmt.Println(result, *h)
}
return result
}
func main() {
nums := []int{5, 9, 3, 1, 2, 8, 4, 7, 6}
fmt.Println(nums)
fmt.Println("-----BEGIN-----")
result := sort(nums)
fmt.Println("----- END -----")
fmt.Println(result)
}
出力結果
[5 9 3 1 2 8 4 7 6]
-----BEGIN-----
[1] [2 3 4 6 7 8 5 9]
[1 2] [3 6 4 9 7 8 5]
[1 2 3] [4 6 5 9 7 8]
[1 2 3 4] [5 6 8 9 7]
[1 2 3 4 5] [6 7 8 9]
[1 2 3 4 5 6] [7 9 8]
[1 2 3 4 5 6 7] [8 9]
[1 2 3 4 5 6 7 8] [9]
[1 2 3 4 5 6 7 8 9] []
----- END -----
[1 2 3 4 5 6 7 8 9]
マージソート
サンプルコード
main.go
package main
import (
"fmt"
)
func sort(nums []int) []int {
if len(nums) == 1 {
return nums
}
halfIndex := len(nums) / 2
leftNums := sortMerge(nums[:halfIndex])
rightNums := sortMerge(nums[halfIndex:])
leftIndex := 0
rightIndex := 0
var result []int
for i := 0; i < len(leftNums)+len(rightNums); i++ {
if len(rightNums) <= rightIndex || (len(leftNums) > leftIndex && leftNums[leftIndex] <= rightNums[rightIndex]) {
result = append(result, leftNums[leftIndex])
leftIndex++
} else {
result = append(result, rightNums[rightIndex])
rightIndex++
}
}
fmt.Println(leftNums, rightNums)
fmt.Println(result)
fmt.Println("-----")
return result
}
func main() {
nums := []int{5, 9, 3, 1, 2, 8, 4, 7, 6}
fmt.Println(nums)
fmt.Println("-----BEGIN-----")
result := sort(nums)
fmt.Println("----- END -----")
fmt.Println(result)
}
出力結果
[5 9 3 1 2 8 4 7 6]
-----BEGIN-----
[5] [9]
[5 9]
-----
[3] [1]
[1 3]
-----
[5 9] [1 3]
[1 3 5 9]
-----
[2] [8]
[2 8]
-----
[7] [6]
[6 7]
-----
[4] [6 7]
[4 6 7]
-----
[2 8] [4 6 7]
クイックソート
サンプルコード
main.go
package main
import (
"fmt"
"math/rand"
"time"
)
func sort(nums []int) []int {
if len(nums) == 1 {
return nums
}
rand.Seed(time.Now().Unix())
index := rand.Intn(len(nums))
var smallerNums []int
var largerNums []int
baseValue := nums[index]
for i := 0; i < len(nums); i++ {
if i == index {
continue
}
value := nums[i]
if baseValue <= value {
largerNums = append(largerNums, value)
} else {
smallerNums = append(smallerNums, value)
}
}
var result []int
if len(smallerNums) > 0 {
result = sortQuick(smallerNums)
}
result = append(result, baseValue)
if len(largerNums) > 0 {
result = append(result, sortQuick(largerNums)...)
}
fmt.Println(smallerNums, baseValue, largerNums)
return result
}
func main() {
nums := []int{5, 9, 3, 1, 2, 8, 4, 7, 6}
fmt.Println(nums)
fmt.Println("-----BEGIN-----")
result := sort(nums)
fmt.Println("----- END -----")
fmt.Println(result)
}
出力結果
[5 9 3 1 2 8 4 7 6]
-----BEGIN-----
[1] 2 [3]
[3 1 2] 4 [5]
[] 8 [9]
[] 7 [9 8]
[5 3 1 2 4] 6 [9 8 7]
----- END -----
[1 2 3 4 5 6 7 8 9]