クイックソートのGolang実装

quicksort.go

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)
}