I just started learning golang and decided to implement some basic sorting algorithms (bubble sort, selection sort, and insertion sort) to try working with packages, slices, and testing infrastructure.
Here's the implementation:
package child_sort
func SortBubble(xs []int) {
for i := range xs {
swapped := false
for j := 1; j < len(xs)-i; j++ {
if xs[j-1] > xs[j] {
xs[j-1], xs[j] = xs[j], xs[j-1]
swapped = true
}
}
if !swapped {
break
}
}
}
func SortSelection(xs []int) {
for i := range xs {
min_i := i
for j := i + 1; j < len(xs); j++ {
if xs[j] < xs[min_i] {
min_i = j
}
}
if min_i != i {
xs[i], xs[min_i] = xs[min_i], xs[i]
}
}
}
func SortInsertion(xs []int) {
for i := 1; i < len(xs); i++ {
for j := i; j > 0; j-- {
if xs[j] < xs[j-1] {
xs[j], xs[j-1] = xs[j-1], xs[j]
}
}
}
}
Unit tests seem to work fine, but when I created benchmarks for these, I got weird results, like these:
go test --bench . --benchmem
PASS
BenchmarkBubble 1 2258469081 ns/op 241664 B/op 1 allocs/op
BenchmarkSelection 1000000000 0.60 ns/op 0 B/op 0 allocs/op
BenchmarkInsertion 1 1180026827 ns/op 241664 B/op 1 allocs/op
ok .../go/src/child_sort 12.976s
What bugs me is that selection sort runs almost instantly and produces zero allocations. Same thing happens to other sorting algos if I decrease the size of the arrays. And the opposite is true, i.e. if I increase the size, selection sort starts to behave sanely.
Here's the tests file:
package child_sort
import (
"math/rand"
"testing"
"time"
)
func generate(size int, min, max int) []int {
rand.Seed(time.Now().UTC().UnixNano())
var xs = make([]int, size, size)
for i := range xs {
xs[i] = min + rand.Intn(max-min)
}
return xs
}
func TestSortBubble(t *testing.T) {
xs := []int{9, 8, 7, 6, 5}
ys := []int{5, 6, 7, 8, 9}
SortBubble(xs)
for i, v := range xs {
if v != ys[i] {
t.Errorf("fail")
}
}
}
func TestSortSelection(t *testing.T) {
xs := []int{1, 2, 9, 6, 2}
ys := []int{1, 2, 2, 6, 9}
SortSelection(xs)
for i, v := range xs {
if v != ys[i] {
t.Errorf("fail")
}
}
}
func TestSortInsertion(t *testing.T) {
xs := []int{1, 2, 9, 6, 2}
ys := []int{1, 2, 2, 6, 9}
SortInsertion(xs)
for i, v := range xs {
if v != ys[i] {
t.Errorf("fail")
}
}
}
func BenchmarkBubble(b *testing.B) {
xs := generate(10000, -100, 100)
/* b.ResetTimer() */
SortBubble(xs)
}
func BenchmarkSelection(b *testing.B) {
xs := generate(10000, -100, 100)
/* b.ResetTimer() */
SortSelection(xs)
}
func BenchmarkInsertion(b *testing.B) {
xs := generate(10000, -100, 100)
/* b.ResetTimer() */
SortInsertion(xs)
}