Goでソートアルゴリズムを実装してみた #1

概要

代表的なソートアルゴリズムのうち、初等的なものをGo言語で実装してみます。
今回対象とするのは以下の通り：

• 挿入ソート
• バブルソート
• 選択ソート
• シェルソート

アルゴリズム自体の説明はしません。

検証環境

• go1.19.2

ソートアルゴリズム

挿入ソート

package main

import "fmt"

func main() {
	a := []int{8, 2, 6, 11, 5}
	insertionSort(a)
	fmt.Println(a)
	// [2 5 6 8 11]
}

// 挿入ソート
func insertionSort(a []int) {
	for i := 1; i < len(a); i++ {
		v := a[i]
		j := i - 1
		for j >= 0 && a[j] > v {
			a[j+1] = a[j]
			j--
		}
		a[j+1] = v
	}
}

バブルソート

package main

import "fmt"

func main() {
	a := []int{8, 2, 6, 11, 5}
	inversion := bubbleSort(a)
	fmt.Println(a)
	// [2 5 6 8 11]
}

// バブルソート
func bubbleSort(a []int) {
	isNotSorted := true
	for i := 0; isNotSorted; i++ {
		// 要素の交換が生じなければソート済み
		isNotSorted = false
		for j := len(a) - 1; j > i; j-- {
			if a[j-1] > a[j] {
				a[j], a[j-1] = a[j-1], a[j]
				isNotSorted = true
			}
		}
	}
}

選択ソート

package main

import "fmt"

func main() {
	a := []int{8, 2, 6, 11, 5}
	selectionSort(a)
	fmt.Println(a)
	// [2 5 6 8 11]
}

// 選択ソート
func selectionSort(a []int) {
	for i := 0; i < len(a); i++ {
		minj := i
		for j := i; j < len(a); j++ {
			if a[j] < a[minj] {
				minj = j
			}
		}
		a[i], a[minj] = a[minj], a[i]
	}
}

シェルソート

package main

import "fmt"

func main() {
	a := []int{8, 2, 6, 11, 5}
	shellSort(a)
	fmt.Println(a)
	// [2 5 6 8 11]
}

// シェルソート
func shellSort(a []int) {
	// 挿入ソートの間隔を表現する数列を生成
	// ここでは g_i+1 = 3 * g_i + 1 を採用
	var g []int
	for i := 1; i <= len(a); i = 3*i + 1 {
		g = append(g, i)
	}

	for i := len(g) - 1; i >= 0; i-- {
		insertionSort(a, g[i])
	}
}

// 挿入ソート
func insertionSort(a []int, g int) {
	for i := g; i < len(a); i++ {
		v := a[i]
		j := i - g
		for j >= 0 && a[j] > v {
			a[j+g] = a[j]
			j = j - g
		}
		a[j+g] = v
	}
}