Goで基本ソートを実装してみる
基本的なソートを空で書けたほうが良いだろうということで、練習してみているnixii.icon
以下は全てintの配列を受け取り、昇順にソートする実装。
最後にそれぞれのテストコードもまとめて書いている。
選択ソート
code:selection_sort.go
/* 選択ソート */
func SelectionSort(arr []int) []int {
for i := 0; i < len(arr)-1; i++ {
minIdx := i
for j := i + 1; j < len(arr); j++ {
minIdx = j
}
}
if i != minIdx {
}
}
return arr
}
挿入ソート
code:insertion_sort.go
/* 挿入ソート */
func InsertionSort(arr []int) []int {
for i := 0; i < len(arr); i++ {
j := i - 1
for j >= 0 && arrj > key { j--
}
}
return arr
}
ヒープソート
code:heap_sort.go
/* ヒープソート */
func heapify(arr []int, n, i int) {
lgst := i
l := lgst*2 + 1
r := lgst*2 + 2
if l < n && arrl > arrlgst { lgst = l
}
if r < n && arrr > arrlgst { lgst = r
}
if lgst != i {
heapify(arr, n, lgst)
}
}
func HeapSort(arr []int) []int {
n := len(arr)
for i := n / 2; i >= 0; i-- {
heapify(arr, n, i)
}
for i := n - 1; i >= 0; i-- {
heapify(arr, i, 0)
}
return arr
}
マージソート
code:merge_sort.go
/* マージソート */
func merge(l, r []int) []int {
ret := make([]int, 0, len(l)+len(r))
i, j := 0, 0
for i < len(l) && j < len(r) {
i++
} else {
j++
}
}
ret = append(ret, li:...) ret = append(ret, rj:...) return ret
}
func MergeSort(arr []int) []int {
n := len(arr)
if n <= 1 {
return arr
}
mid := n / 2
return merge(l, r)
}
クイックソート
code:quick_sort.go
/* クイックソート */
func partition(arr []int, l, r int) int {
// スワップが発生し、位置が確定した値のindex
storedIdx := l
// arriを参照してl→rにかけて走査していき、pivotより小さければ // 一番左の値arr[storedIdx]と走査対象の値であるarr[i]をスワップする。
for i := l; i < r; i++ {
storedIdx++
}
}
// 最後にpivot(つまり、arrr)を正しい位置にスワップ。 // この時点で、少なくともpivot自身の位置は正しいことになる。
return storedIdx
}
func QuickSort(arr []int, l, r int) []int {
if l < r {
pivot := partition(arr, l, r)
QuickSort(arr, l, pivot-1)
QuickSort(arr, pivot+1, r)
}
return arr
}
-.icon
テストコード
code:tests.go
package sortpkg
import (
"reflect"
"testing"
)
func TestSelectionSort(t *testing.T) {
input := []int{64, 25, 12, 22, 11}
expected := []int{11, 12, 22, 25, 64}
result := SelectionSort(input)
if !reflect.DeepEqual(result, expected) {
t.Errorf("Expected %v, got %v", expected, result)
}
}
func TestInsertionSort(t *testing.T) {
input := []int{64, 25, 12, 22, 11}
expected := []int{11, 12, 22, 25, 64}
result := InsertionSort(input)
if !reflect.DeepEqual(result, expected) {
t.Errorf("Expected %v, got %v", expected, result)
}
}
func TestHeapSort(t *testing.T) {
input := []int{64, 25, 12, 22, 11}
expected := []int{11, 12, 22, 25, 64}
result := HeapSort(input)
if !reflect.DeepEqual(result, expected) {
t.Errorf("Expected %v, got %v", expected, result)
}
}
func TestMergeSort(t *testing.T) {
input := []int{64, 25, 12, 22, 11}
expected := []int{11, 12, 22, 25, 64}
result := MergeSort(input)
if !reflect.DeepEqual(result, expected) {
t.Errorf("Expected %v, got %v", expected, result)
}
}
func TestQuickSort1(t *testing.T) {
input := []int{64, 25, 12, 22, 11}
expected := []int{11, 12, 22, 25, 64}
result := QuickSort(input, 0, len(input)-1)
if !reflect.DeepEqual(result, expected) {
t.Errorf("Expected %v, got %v", expected, result)
}
}
func TestQuickSort2(t *testing.T) {
input := []int{10, 7, 8, 9, 1, 5}
expected := []int{1, 5, 7, 8, 9, 10}
result := QuickSort(input, 0, len(input)-1)
if !reflect.DeepEqual(result, expected) {
t.Errorf("Expected %v, got %v", expected, result)
}
}