最近またアルゴリズムの勉強を始めようと思い、まずはバブルソートを作ってみました。以前はこういう系はPythonでやってたんですが、最近Goの勉強もしてるのでGoで作ってみました。
こちらのオンラインエディタが勝手にフォーマットもしてくれて便利でした。
https://go.dev/play/
コード
package main
import "fmt"
func main() {
numbers := [10]int{9, 8, 7, 6, 5, 4, 3, 2, 1, 0}
switched := true
for maxIndex := len(numbers) - 1; switched && 0 < maxIndex; maxIndex-- {
switched = false
for i := 0; i < maxIndex; i++ {
left := numbers[i]
right := numbers[i+1]
if left > right {
numbers[i] = right
numbers[i+1] = left
switched = true
}
}
}
fmt.Println(numbers) // [0 1 2 3 4 5 6 7 8 9]
}
バブルソートの考え方
- 配列の右端か左端の隣り合う2つの要素を見比べて、あるべき順序と逆であれば入れ替える（たとえば「小→大」になってほしい配列で[5,1]っていう並びがあれば入れ替える）
- 上記の処理を1個ずつ位置をずらしながら配列の全長に対して行っていく（配列の左から1個目と2個目、2個目と3個目...）
- 上記の処理をワンセット行うと最大もしくは最小の数が配列の右端もしくは左端にたどり着く（たとえば「小→大」にしたい配列で左→右に並び替えを行うと最大の数が右端に来る）
- 確定している最大もしくは最小の値は抜いて残りの配列に対して同じソートを行っていく
- 並び替えが発生しなくなるもしくは比較対象の配列の長さが1になるまで行う
今回の配列の並び順の変化はこうなりました
[8 9 7 6 5 4 3 2 1 0]
[8 7 9 6 5 4 3 2 1 0]
[8 7 6 9 5 4 3 2 1 0]
[8 7 6 5 9 4 3 2 1 0]
[8 7 6 5 4 9 3 2 1 0]
[8 7 6 5 4 3 9 2 1 0]
[8 7 6 5 4 3 2 9 1 0]
[8 7 6 5 4 3 2 1 9 0]
[8 7 6 5 4 3 2 1 0 9]
[7 8 6 5 4 3 2 1 0 9]
[7 6 8 5 4 3 2 1 0 9]
[7 6 5 8 4 3 2 1 0 9]
[7 6 5 4 8 3 2 1 0 9]
[7 6 5 4 3 8 2 1 0 9]
[7 6 5 4 3 2 8 1 0 9]
[7 6 5 4 3 2 1 8 0 9]
[7 6 5 4 3 2 1 0 8 9]
[6 7 5 4 3 2 1 0 8 9]
[6 5 7 4 3 2 1 0 8 9]
[6 5 4 7 3 2 1 0 8 9]
[6 5 4 3 7 2 1 0 8 9]
[6 5 4 3 2 7 1 0 8 9]
[6 5 4 3 2 1 7 0 8 9]
[6 5 4 3 2 1 0 7 8 9]
[5 6 4 3 2 1 0 7 8 9]
[5 4 6 3 2 1 0 7 8 9]
[5 4 3 6 2 1 0 7 8 9]
[5 4 3 2 6 1 0 7 8 9]
[5 4 3 2 1 6 0 7 8 9]
[5 4 3 2 1 0 6 7 8 9]
[4 5 3 2 1 0 6 7 8 9]
[4 3 5 2 1 0 6 7 8 9]
[4 3 2 5 1 0 6 7 8 9]
[4 3 2 1 5 0 6 7 8 9]
[4 3 2 1 0 5 6 7 8 9]
[3 4 2 1 0 5 6 7 8 9]
[3 2 4 1 0 5 6 7 8 9]
[3 2 1 4 0 5 6 7 8 9]
[3 2 1 0 4 5 6 7 8 9]
[2 3 1 0 4 5 6 7 8 9]
[2 1 3 0 4 5 6 7 8 9]
[2 1 0 3 4 5 6 7 8 9]
[1 2 0 3 4 5 6 7 8 9]
[1 0 2 3 4 5 6 7 8 9]
[0 1 2 3 4 5 6 7 8 9]
Goに関しての個人的ポイント
外側のループはWhileのイメージだったけど、GoではWhileが存在しない（!）のでforを使った
for maxIndex := len(numbers) - 1; switched && 0 < maxIndex; maxIndex-- {}