[アルゴリズム] クイックソートの実装(Go言語編)

何度かGo言語でソートアルゴリズム作ってきましたが、今回は初めてelse if文を使った事と、while文がgo言語に無いこと知り、少し戸惑ってしまいました。
C言語のようにポインタ使って処理しようかと思ったんですが、あまり冒険せずにそのままストレートなソースで書いてます。
ソース
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 |
package main import "fmt" func mid(x int , y int , z int) int { if x < y { if y < z { return y } else if z < x { return x } else { return z } } else { if z < y { return y } else if x < z { return x } else { return z } } } func quickSort(numbers []int , begin int , end int) []int { // 左辺と右辺の開始位置を定義 var left int = begin var right int = end // ピボット(中央の値) mid_num := int (left + ((right - left)/2)) var pivot int = mid(numbers[left] , numbers[mid_num] , numbers[right]) // ソート処理実行(pivotが交差するまで続行) for { // 左辺のpivotよりも大きい値見つける for numbers[left] < pivot {left++} // 右辺のpivotよりも小さい値をみつける for numbers[right] > pivot {right--} //pivotが交差したら終了 if(left >= right){break} // 値の入れ替え処理 var tmp int = numbers[left] numbers[left] = numbers[right] numbers[right] = tmp // 繰り返し対応 left++ right-- } // pivotの左辺のソート処理 if begin < left {numbers = quickSort(numbers , begin , left-1)} // pivotの右辺のソート処理 if right < end {numbers = quickSort(numbers , right+1 , end)} return numbers } func main(){ numbers := []int{10,2,12,7,16,8,13} num2 := quickSort(numbers , 0 , len(numbers)-1) fmt.Println(num2) } |
実行
1 2 |
$ go run quickSort.go [2 7 8 10 12 13 16] |
※エラー出まくりましたが、多くがsyntaxエラーだったので、成功結果のみ載せてます・・・
解説
whileが無い・・・
Go言語にはwhile文が無いですが、その分for文が強力な機能を持っています。
ていうか、他の言語より、Go言語のfor文が使いやすいんですけど、これいいですね。
ちなみに、Go言語のwhileの代わりのfor文は、条件無しでfor{…}と書くだけで、任意の段階でbreakすればいいので
無限loopバグがあれば地獄ですが、それでもプログラム言語としては、理解しやすいと思います。
else ifの書き方
何度もsyntaxになったのがif文の書き方で、他の言語では、{}の改行などあまりシビアに気にしなくていいのに、Go言語では下記のように書かないとイケないようです。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
if y < z { return y } else if z < x { return x } else { return z } $ go run quickSort.go # command-line-arguments ./quickSort.go:10: syntax error: unexpected else, expecting } ./quickSort.go:13: syntax error: unexpected else, expecting } |
1 2 3 4 5 6 7 |
if y < z { return y } else if z < x { return x } else { return z } |
個人的に、上記の書き方をしてきたので、この形固定というのは非常に心苦しい・・・が、我慢するとしよう。
変数宣言
書き方が複数あり、とても悩ましい仕様の一つである変数の宣言だが、少し気になるポイントを書いておく。
1 2 3 4 5 6 7 8 9 |
// 整数の宣言 1 var hoge int hoge = 100 // 整数の宣言 2 var hoge int = 100 //整数の宣言 3 hoge := int(100) |
2番が書きやすいかな〜
なんでこんなに種類があるのか不明ですが、慣れるしかないですね。
参考リンク
クイックソート
解説
Javascript
PHP
Python
Shell
Awk
C言語
Go言語