🍣
Goでソートアルゴリズムを実装してみた #1
概要
代表的なソートアルゴリズムのうち、初等的なものをGo言語で実装してみます。
今回対象とするのは以下の通り:
- 挿入ソート
- バブルソート
- 選択ソート
- シェルソート
アルゴリズム自体の説明はしません。
検証環境
- go1.19.2
ソートアルゴリズム
挿入ソート
package main
import "fmt"
func main() {
a := []int{8, 2, 6, 11, 5}
insertionSort(a)
fmt.Println(a)
// [2 5 6 8 11]
}
// 挿入ソート
func insertionSort(a []int) {
for i := 1; i < len(a); i++ {
v := a[i]
j := i - 1
for j >= 0 && a[j] > v {
a[j+1] = a[j]
j--
}
a[j+1] = v
}
}
バブルソート
package main
import "fmt"
func main() {
a := []int{8, 2, 6, 11, 5}
inversion := bubbleSort(a)
fmt.Println(a)
// [2 5 6 8 11]
}
// バブルソート
func bubbleSort(a []int) {
isNotSorted := true
for i := 0; isNotSorted; i++ {
// 要素の交換が生じなければソート済み
isNotSorted = false
for j := len(a) - 1; j > i; j-- {
if a[j-1] > a[j] {
a[j], a[j-1] = a[j-1], a[j]
isNotSorted = true
}
}
}
}
選択ソート
package main
import "fmt"
func main() {
a := []int{8, 2, 6, 11, 5}
selectionSort(a)
fmt.Println(a)
// [2 5 6 8 11]
}
// 選択ソート
func selectionSort(a []int) {
for i := 0; i < len(a); i++ {
minj := i
for j := i; j < len(a); j++ {
if a[j] < a[minj] {
minj = j
}
}
a[i], a[minj] = a[minj], a[i]
}
}
シェルソート
package main
import "fmt"
func main() {
a := []int{8, 2, 6, 11, 5}
shellSort(a)
fmt.Println(a)
// [2 5 6 8 11]
}
// シェルソート
func shellSort(a []int) {
// 挿入ソートの間隔を表現する数列を生成
// ここでは g_i+1 = 3 * g_i + 1 を採用
var g []int
for i := 1; i <= len(a); i = 3*i + 1 {
g = append(g, i)
}
for i := len(g) - 1; i >= 0; i-- {
insertionSort(a, g[i])
}
}
// 挿入ソート
func insertionSort(a []int, g int) {
for i := g; i < len(a); i++ {
v := a[i]
j := i - g
for j >= 0 && a[j] > v {
a[j+g] = a[j]
j = j - g
}
a[j+g] = v
}
}
Discussion