今さらながら、ソートアルゴリズムの復習をします。
まずは基礎的な バブルソート から始めてみます。
バブルソート
バブルソートは隣り合う要素の大小を比較して並び替えを行う整列方法です。
並び替えの過程でデータが上下に移動する様子が「泡」に例えられたことからこのような名前となったようです。
直感的に分かりやすく、ソートアルゴリズムの基礎となるアルゴリズムです。
また、整列方法の特徴から「隣接交換法」とも呼ばれます。
計算量
データ数がNの場合、O(N2)のオーダーとなります。
このため、データ数が増えるほどに並び替えの時間がかかる効率の悪い整列法です。
詳しくはこの辺りを。
http://www.ics.kagoshima-u.ac.jp/~fuchida/edu/algorithm/sort-algorithm/bubble-sort.html
https://www.akita-pu.ac.jp/system/elect/comp1/kusakari/japanese/teaching/SoftTech/2005/note/4/Slide19.html
Go で書いてみよう
実用はしませんが理解のためコードを書いてみます。
int型のスライスを昇順に並び替えます。
package main
import (
"fmt"
"strconv"
)
func main() {
arrayzor := []int{6, 4, 2, 7, 9, 0, 5, 3, 1, 8}
fmt.Printf("ソート前の値: %v\n", arrayzor)
// 要素数-1回 繰り返す
k := len(arrayzor) - 1
for i := 0; i < k; i++ {
fmt.Printf("%v巡目\n", i+1)
// 最後の要素から順番に比較をする
for j := k; j > i; j-- {
// 出力する文字列の処理
s := "["
for key, val := range arrayzor {
if key == j-1 || key == j {
s = s + "(" + strconv.Itoa(val) + ")"
} else {
s = s + strconv.Itoa(val)
}
if key != k {
s = s + " "
}
}
// 一つ前の要素と比較
if arrayzor[j-1] > arrayzor[j] {
// 一つ前の要素のほうが大きければ入れ替える
arrayzor[j-1], arrayzor[j] = arrayzor[j], arrayzor[j-1]
s = s + "] > 入れ替え！\n"
} else {
s = s + "]\n"
}
fmt.Printf("%s", s)
}
fmt.Printf("%v巡目終了後の値: %v\n\n", i+1, arrayzor)
}
fmt.Printf("ソート後の値: %v\n", arrayzor)
}
これで、go run main.go とすると以下のようにソートされていく過程が出力されます。
()で囲まれている2つの値が比較している要素を表します。
左の要素のほうが大きい値の場合、要素の入れ替えがおこなわれます。
ソート前の値: [6 4 2 7 9 0 5 3 1 8]
1巡目
[6 4 2 7 9 0 5 3 (1) (8)]
[6 4 2 7 9 0 5 (3) (1) 8] > 入れ替え！
[6 4 2 7 9 0 (5) (1) 3 8] > 入れ替え！
[6 4 2 7 9 (0) (1) 5 3 8]
[6 4 2 7 (9) (0) 1 5 3 8] > 入れ替え！
[6 4 2 (7) (0) 9 1 5 3 8] > 入れ替え！
[6 4 (2) (0) 7 9 1 5 3 8] > 入れ替え！
[6 (4) (0) 2 7 9 1 5 3 8] > 入れ替え！
[(6) (0) 4 2 7 9 1 5 3 8] > 入れ替え！
1巡目終了後の値: [0 6 4 2 7 9 1 5 3 8]
2巡目
[0 6 4 2 7 9 1 5 (3) (8)]
[0 6 4 2 7 9 1 (5) (3) 8] > 入れ替え！
[0 6 4 2 7 9 (1) (3) 5 8]
[0 6 4 2 7 (9) (1) 3 5 8] > 入れ替え！
[0 6 4 2 (7) (1) 9 3 5 8] > 入れ替え！
[0 6 4 (2) (1) 7 9 3 5 8] > 入れ替え！
[0 6 (4) (1) 2 7 9 3 5 8] > 入れ替え！
[0 (6) (1) 4 2 7 9 3 5 8] > 入れ替え！
2巡目終了後の値: [0 1 6 4 2 7 9 3 5 8]
3巡目
[0 1 6 4 2 7 9 3 (5) (8)]
[0 1 6 4 2 7 9 (3) (5) 8]
[0 1 6 4 2 7 (9) (3) 5 8] > 入れ替え！
[0 1 6 4 2 (7) (3) 9 5 8] > 入れ替え！
[0 1 6 4 (2) (3) 7 9 5 8]
[0 1 6 (4) (2) 3 7 9 5 8] > 入れ替え！
[0 1 (6) (2) 4 3 7 9 5 8] > 入れ替え！
3巡目終了後の値: [0 1 2 6 4 3 7 9 5 8]
4巡目
[0 1 2 6 4 3 7 9 (5) (8)]
[0 1 2 6 4 3 7 (9) (5) 8] > 入れ替え！
[0 1 2 6 4 3 (7) (5) 9 8] > 入れ替え！
[0 1 2 6 4 (3) (5) 7 9 8]
[0 1 2 6 (4) (3) 5 7 9 8] > 入れ替え！
[0 1 2 (6) (3) 4 5 7 9 8] > 入れ替え！
4巡目終了後の値: [0 1 2 3 6 4 5 7 9 8]
5巡目
[0 1 2 3 6 4 5 7 (9) (8)] > 入れ替え！
[0 1 2 3 6 4 5 (7) (8) 9]
[0 1 2 3 6 4 (5) (7) 8 9]
[0 1 2 3 6 (4) (5) 7 8 9]
[0 1 2 3 (6) (4) 5 7 8 9] > 入れ替え！
5巡目終了後の値: [0 1 2 3 4 6 5 7 8 9]
6巡目
[0 1 2 3 4 6 5 7 (8) (9)]
[0 1 2 3 4 6 5 (7) (8) 9]
[0 1 2 3 4 6 (5) (7) 8 9]
[0 1 2 3 4 (6) (5) 7 8 9] > 入れ替え！
6巡目終了後の値: [0 1 2 3 4 5 6 7 8 9]
7巡目
[0 1 2 3 4 5 6 7 (8) (9)]
[0 1 2 3 4 5 6 (7) (8) 9]
[0 1 2 3 4 5 (6) (7) 8 9]
7巡目終了後の値: [0 1 2 3 4 5 6 7 8 9]
8巡目
[0 1 2 3 4 5 6 7 (8) (9)]
[0 1 2 3 4 5 6 (7) (8) 9]
8巡目終了後の値: [0 1 2 3 4 5 6 7 8 9]
9巡目
[0 1 2 3 4 5 6 7 (8) (9)]
9巡目終了後の値: [0 1 2 3 4 5 6 7 8 9]
ソート後の値: [0 1 2 3 4 5 6 7 8 9]
このように、一番小さい値がどんどん左側へ移動して行っているのが分かりますね。
出力文字列の処理とかがごちゃごちゃしていますが、ソート部分だけを書いたコードはググれば出てくるでしょう。
参考
http://www.ics.kagoshima-u.ac.jp/~fuchida/edu/algorithm/sort-algorithm/bubble-sort.html
https://ja.wikipedia.org/wiki/%E3%83%90%E3%83%96%E3%83%AB%E3%82%BD%E3%83%BC%E3%83%88
https://github.com/davidwang2007/golang-learning/blob/master/src/sorter/algorithm/bubblesort/bubblesort.go
https://www.akita-pu.ac.jp/system/elect/comp1/kusakari/japanese/teaching/SoftTech/2005/note/4/Slide19.html
http://www.geocities.jp/m_hiroi/golang/yagp01.html#ans10