ソートと向き合う
そろそろソートについてしっかり向き合わないといけないと思った。
なんか調べてみるといろいろ種類があるらしい。
自分が最初に数字のスライスをソートする処理をgolangで書いたものがこちら
いわゆるバブルソートというやつ。
一つ後のやつを比較して順番をどんどん入れ替える。
一回も順番が入れ替わらなかったら終わり。
実装がめっちゃ簡単でわかりやすい。
func Sort(slice int) int {
for {
flag := true
for i := 0; i < len(slice)-1; i++ {
if slice[i] > slice[i+1] {
temp := slice[i]
slice[i] = slice[i + 1]
slice[i + 1] = temp
flag = false
}
}
if flag {
break
}
}
return slice
}
今はクイックソートというものが一番早いらしい。つよそう
早速説明を見て実装をする。
func quickSort(slice int) int {
var lowerSlice int
var equalslice int
var upperSlice []int
// スライスの要素数が1か0の時はソートしようが無いのでそのまま返す
if len(slice) <= 1 {
return slice
}
// 軸要素をランダムに一つ選ぶ
rand.Seed(time.Now().UnixNano())
pivot := rand.Intn(len(slice))
pivotVal := slice[pivot]
// pivotより大きい、小さい、同じやつを詰める
for _, v := range slice {
if v > pivotVal {
upperSlice = append(upperSlice, v)
}
if v < pivotVal {
lowerSlice = append(lowerSlice, v)
}
if v == pivotVal {
equalslice = append(equalslice, v)
}
}
// 大きいやつと小さいやつはまたソートを行う
lowerSlice = quickSort(lowerSlice)
upperSlice = quickSort(upperSlice)
// 小さいやつに同じやつを追加
for _, v := range equalslice {
lowerSlice = append(lowerSlice, v)
}
// 大きいやつを追加
for _, v := range upperSlice {
lowerSlice = append(lowerSlice, v)
}
return lowerSlice
}
再起関数とかいうやつ初めて使った。
これであってるのか....？
一応動作確認はした。
試しに時間を計測してみた。
ランダムな要素が10万個入ったスライスをソートする。
これを3回実行。
18.160090秒
17.948176秒
18.061429秒
0.450110秒
0.442886秒
0.445114秒
速すぎる...
