Skip to content

Instantly share code, notes, and snippets.

@Hayao0819
Last active June 2, 2023 05:45
Show Gist options
  • Save Hayao0819/1f22a577ca04b3661155909d99585085 to your computer and use it in GitHub Desktop.
Save Hayao0819/1f22a577ca04b3661155909d99585085 to your computer and use it in GitHub Desktop.
クイックソートのGolang実装
package main
import (
"fmt"
"math"
"math/rand"
"os"
"strconv"
)
var called int=0 // quick_sort関数の実行回数
// 入力: arr=配列 baseindex=基準値となる値のインデックス
// 出力: 小さいほう 大きいほう
// 出力に基準値のindexの要素は含まれない
func compare(arr []int, baseindex int)([]int, []int){
bigger := []int{}
smaller:= []int{}
for i, v := range arr {
if i==baseindex{
continue
}
if v > arr[baseindex] {
bigger = append(bigger, v)
}else{
smaller = append(smaller, v)
}
}
return smaller, bigger
}
func quick_sort(arr []int) ([]int){
called++ // 呼び出し回数
if len(arr) <= 1{ // 値が1つのときに終了
return arr
}
s, b := compare(arr, len(arr)/2) // 比較を実行
b=quick_sort(b) // 大きい方で再帰的に実行
s=quick_sort(s) // 小さい方で再帰的に実行
return join_array(s, []int{arr[len(arr)/2]} , b) // 小さい方 + 基準値 + 大きい方で結合
}
// クイックソートを実行
func run_quicksort(len int){
data := random(len)
fmt.Printf("Length: %d\n", len)
fmt.Printf("Source: %v\n", data)
fmt.Printf("Sorted: %v\n", quick_sort(data))
fmt.Printf("Called: %d\n", called)
fmt.Printf(" Order: %v\n", math.Log2(float64(len))*float64(len))
}
// 任意の長さの乱数の配列を作成
func random(time int)([]int){
slice := []int{}
for i:=0; i<time; i++{
slice=append(slice, rand.Intn(20))
}
return slice
}
// int型配列を結合
func join_array(arr ...[]int)([]int){
r := []int{}
for _, i := range arr {
r = append(r, i...)
}
return r
}
func main(){
def := 20 // デフォルト値
if len(os.Args) < 2{ // 引数がない場合
run_quicksort(def)
os.Exit(0)
}
// 引数がある場合
value, err := strconv.Atoi(os.Args[1])
if err != nil{ // 引数が整数じゃない場合異常終了
fmt.Fprintln(os.Stderr, err)
os.Exit(-1)
}
run_quicksort(value)
os.Exit(0)
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment