Golangで代表的なソートの復習

はじめに

Go言語で代表的なソートのプログラミングを実装してみました。
目的はスライスの練習とソートの復習、Goの練習です。
Go初心者なので書き方云々なんか気になるところはコメントください！
注) アルゴリズム理解が目的なのでsortライブラリは用いてないです。

今のところ以下作成しました。

• インサーションソート (Insertion sort)
• マージソート (Merge sort)
• クイックソート (Quick sort)
• バブルソート（Bubble sort）

github

順次追加予定です。
自分のメモ用にQiitaに載せますが自分より初心者の方に役に立てばと思います。
学校の課題などの参考になさってください。
それぞれパッケージにまとめてimportする形にしました。
入力と出力どちらも[]intのスライスです。
他の型にする場合は適当に変更すれば良いと思います

以下に実行コードとそれぞれのコードを載せます。
実行時間計算してみましたが、一回しか実行していないのでそんなに役には立たないです。

実行コード

ファイル構造
sortlib
├mysort
│ ├bubble.go
│ ├insertion.go
│ ├merge.go
│ └quick.go
└main.go

main.go

// Example of execution

package main

import (
	"fmt"
	"math/rand"
	"time"

	"../sortlib/mysort"
)

func main() {
	rand.Seed(time.Now().Unix()) //Seed setting
	n := 10000 //data size

	data := make([]int, n) // create slice
	for i := 0; i < n; i++ {
		data[i] = rand.Intn(100)
	}

	fmt.Println(data)
	start := time.Now() 
	// Choose what you like ==================================
	fmt.Println(mysort.Insertionsort(data))
	//fmt.Println(mysort.Mergesort(data))
	//fmt.Println(mysort.Quicksort(data))
    //fmt.Println(mysort.Bubblesort(data))
	//====================================Uai================
	end := time.Now()
	fmt.Printf("%fs\n", (end.Sub(start)).Seconds()) //Execution time
}

インサーションソート (Insertion sort)

insertion.go

package mysort

func Insertionsort(s []int) []int {
	for i := 1; i < len(s); i++ {
		j := i - 1
		temp := s[i]
		for j > -1 && s[j] > temp {
			s[j+1] = s[j]
			j--
		}
		s[j+1] = temp
	}
	return s
}

実行時間
データ　10000個　0 ~ 100の整数
0.217022s

マージソート (Merge sort)

merge.go

package mysort

func Mergesort(s []int) []int {
	var result []int
	if len(s) < 2 {
		return s
	}

	mid := int(len(s) / 2)
	r := Mergesort(s[:mid])
	l := Mergesort(s[mid:])
	i, j := 0, 0

	for i < len(r) && j < len(l) {
		if r[i] > l[j] {
			result = append(result, l[j])
			j++
		} else {
			result = append(result, r[i])
			i++
		}
	}

	result = append(result, r[i:]...)
	result = append(result, l[j:]...)

	return result
}

実行時間
データ　10000個　0 ~ 100の整数
0.096361s

クイックソート (Quick sort)

quick.go

package mysort

func Quicksort(s []int) []int {
	if len(s) == 1 || len(s) == 0 { //list size 0 or 1 is no sort
		return s
	} else {
		pivot := s[0] //make a pivot first in the list
		place := 0

		for j := 0; j < len(s)-1; j++ {
			if s[j+1] < pivot { // if it is smaller than the pivot
				s[j+1], s[place+1] = s[place+1], s[j+1]
				place++
			}
		}
		s[0], s[place] = s[place], s[0]

		first := Quicksort(s[:place])
		second := Quicksort(s[place+1:])
		first = append(first, s[place])

		first = append(first, second...)
		return first
	}

}

実行時間
データ　10000個　0 ~ 100の整数
0.094660s

バブルソート (Bubble sort)

bubble.go

package mysort

func Bubblesort(s []int) []int {
	for i := 0; i < len(s); i++ {
		for j := i + 1; j < len(s); j++ {
			if s[i] > s[j] {
				s[i], s[j] = s[j], s[i]
			}
		}
	}
	return s
}

実行時間
データ　10000個　0 ~ 100の整数
0.049021s

##総括
やる気があれば他の言語と比較などしてみます。
あと、クイックソートはO(log(n))まで落とせるらしいので今度はそちらもやってみます。

色々なアルゴリズム実装してみたいのでこんなのあるよ！を密かに募集してます！

##参考

• 大学４年間のデータサイエンスが10時間でざっと学べる　久野亮平　木脇太一　著
• 各　Wikipedia