ど定番のアルゴリズムをGoで書いてみた話

この記事は？

先日、Goでは初めてソートアルゴリズムを書いてみたのでその備忘録としてまとめていこうと思います。

バブルソート

バブルソートとは、以下の順番でソートしていく手法です。

1. 一つ右の数字と比較して、小さければ左に移動させる
2. 全要素で行う
   計算量はO(N^2)となるので、クイックソートなどに比べると遅いソートになります。

コード

func main() {
	slc := []int{10, 8, 2, 5, 9, 6, 1, 3, 4, 7}
	sort := bubbleSort(slc)
}

func bubbleSort(slc []int) []int {
	for i := 0; i < len(slc); i++ {
		for j := i + 1; j < len(slc); j++ {
			if slc[i] > slc[j] {
				tmp := slc[i]
				slc[i] = slc[j]
				slc[j] = tmp
			}
		}
	}
	return slc
}

セレクションソート

セレクションソートとは、以下の順番でソートしていく手法です。

1. 配列の中から最小値を探す
2. 最小値を一番左の要素と入れ替える
3. ２要素目から1を繰り返す
   こちらも、バブルソート同様、計算量はO(N^2)となるので、クイックソートなどに比べると遅いソートになります。

コード

func main() {
	slc := []int{10, 8, 2, 5, 9, 6, 1, 3, 4, 7}
	sort := selectionSort(slc)
}

func selectionSort(slc []int) []int {
	for i := 0; i < len(slc); i++ {
		idx := i
		tmpSmall := slc[i]
		for j := 0 + i + 1; j < len(slc); j++ {
			if tmpSmall > slc[j] {
				tmpSmall = slc[j]
				idx = j
			}
		}
		tmp := slc[i]
		slc[i] = slc[idx]
		slc[idx] = tmp
	}
	return slc
}

マージソート

マージソートとは、以下の順番でソートしていく手法です。

1. 要素数が1になるまで分割をしていく
2. 並び替えながら、分割した要素を合体させる(要素数1→2→４→8...となる)
3. 始めの要素数になるまで繰り返す

こちらのソートでは再帰が出てくるため、上2つのソートと比べると複雑です。
しかし、計算量はO(log N)となるため、上記2つのソートと比べると計算量としては優れたソートと呼べると思います。

コード

func main() {
	array := []int{4, 9, 1, 3, 5, 7, 6, 10, 8, 2}
	sorted := mergeSort(array)
	fmt.Println(sorted)
}
func mergeSort(array []int) []int {
	if len(array) == 1 {
		return array
	}
	if len(array) == 2 {
		if array[0] > array[1] {
			tmp := array[0]
			array[0] = array[1]
			array[1] = tmp
		}
		return array
	}

	left := array[:len(array)/2]
	leftSorted := mergeSort(left)

	right := array[len(array)/2:]
	rightSorted := mergeSort(right)

	sorted := []int{}
	n := len(leftSorted) + len(rightSorted)
	for i := 0; i < n; i++ {
		if leftSorted[0] > rightSorted[0] {
			sorted = append(sorted, rightSorted[0])
			rightSorted = rightSorted[1:]
			if len(rightSorted) == 0 {
				sorted = append(sorted, leftSorted...)
				return sorted
			}
		} else {
			sorted = append(sorted, leftSorted[0])
			leftSorted = leftSorted[1:]
			if len(leftSorted) == 0 {
				sorted = append(sorted, rightSorted...)
				return sorted
			}
		}
	}
	fmt.Println(sorted)
	return sorted
}