Sorts in Go

sorts.go

// Code accompanying blog post: http://www.jasondsouza.org/post/sorting/
//
// Package sorts provides implementations of various comparison based sorting algorithms.
// All the sorts work in place, and expect the input data to satisfy the
// sort.Interface interface from the standard library.
// In addition to the collection data to be sorted, they take a start and end index
// (a and b respectively), which cause the slice [a, b) of the collection to be
// sorted. Specifying a = 0 and b = len(collection) will sort the entire collection.
package sorts

import "sort"

// Bubblesort works by "bubbling" the largest element in the data
// collection to the end, and repeating until all elements are sorted..
func BubbleSort(data sort.Interface, a, b int) {
	performedSwap := false
	for i := a + 1; i < b; i++ {
		if data.Less(i, i-1) {
			performedSwap = true
			data.Swap(i, i-1)
		}
	}

	if performedSwap {
		// we know that the largest element is at the end, now sort the rest of the list
		BubbleSort(data, a, b-1)
	}
	// if no swap was performed, the list is sorted
	return
}

// Selection sort works by selecting the smallest element in the collection,
// and swapping it to the front. This process is repeated until all of the
// elements are sorted.
func SelectionSort(data sort.Interface, a, b int) {
	if b <= a {
		return
	}
	smallestElementIdx := a
	for i := a + 1; i < b; i++ {
		if data.Less(i, smallestElementIdx) {
			smallestElementIdx = i
		}
	}
	data.Swap(a, smallestElementIdx)

	SelectionSort(data, a+1, b)
}

// Insertion sort works by going through the collection, and inserting each
// element into the correct place at the (sorted) front of the collection.
func InsertionSort(data sort.Interface, a, b int) {
	for i := a + 1; i < b; i++ {
		for j := i; j > a && data.Less(j, j-1); j-- {
			data.Swap(j, j-1)
		}
	}
}

// Merge sort works by recursively merging sorted sub-collections together
// until the entire collection has been sorted.
func MergeSort(data sort.Interface, a, b int) {
	if b-a < 2 {
		return
	}

	mid := a + (b-a)/2
	MergeSort(data, a, mid)
	MergeSort(data, mid, b)
	merge(data, a, mid, b)
}

// Merges (in place) the two sorted logical collections represented by the indices
// [a, m) and [m, b) of the input data collection. The result is a sorted logical
// collection that extends from a to b.
func merge(data sort.Interface, a, m, b int) {
	// check if the two collections are already sorted
	if data.Less(m-1, m) {
		return
	}

	i, j := a, m
	for i < j && j < b {
		if data.Less(i, j) {
			i++
		} else {
			j++
			shiftRight(data, i, j)
			// update i pointer to take the shift into account
			i++
		}
	}
	// whatever remains is already in the right place
}

// Shifts the data elements in the collection slice data[a,b) to the right
// by one element, with wraparound, meaning the last element in the slice is now
// the first element
func shiftRight(data sort.Interface, a, b int) {
	for i := b - 1; i > a; i-- {
		data.Swap(i, i-1)
	}
}

// Quicksort works by picking a pivot element, and moving everything less than
// the pivot to its left, and everything greater than the pivot to its right.
// Recursing on the left and right sublists results in a sorted list.
func QuickSort(data sort.Interface, a, b int) {
	if b-a < 2 {
		return
	}

	pivot := b - 1
	finalPivotSpot := a
	for i := a; i < b; i++ {
		if data.Less(i, pivot) {
			data.Swap(i, finalPivotSpot)
			finalPivotSpot++
		}
	}
	data.Swap(finalPivotSpot, pivot)
	QuickSort(data, a, finalPivotSpot)
	QuickSort(data, finalPivotSpot+1, b)
}

sorts_test.go

package sorts

import (
	"math/rand"
	"sort"
	"testing"
)

const (
	TEST_DATA_LENGTH = 1000
)

func generateTestData(length int) sort.IntSlice {
	data := make(sort.IntSlice, length)
	for i := 0; i < length; i++ {
		data[i] = rand.Intn(length)
	}
	return data
}

func TestBubbleSort(t *testing.T) {
	data := generateTestData(TEST_DATA_LENGTH)
	t.Log("Input data:", data)

	BubbleSort(data, 0, TEST_DATA_LENGTH)
	t.Log("Output data:", data)

	if !sort.IsSorted(data) {
		t.Error("BubbleSort result is not properly sorted")
	}
}

func TestSelectionSort(t *testing.T) {
	data := generateTestData(TEST_DATA_LENGTH)
	t.Log("Input data:", data)

	SelectionSort(data, 0, TEST_DATA_LENGTH)
	t.Log("Output data:", data)

	if !sort.IsSorted(data) {
		t.Error("SelectionSort result is not properly sorted")
	}
}

func TestInsertionSort(t *testing.T) {
	data := generateTestData(TEST_DATA_LENGTH)
	t.Log("Input data:", data)

	InsertionSort(data, 0, TEST_DATA_LENGTH)
	t.Log("Output data:", data)

	if !sort.IsSorted(data) {
		t.Error("InsertionSort result is not properly sorted")
	}
}

func TestMergeSort(t *testing.T) {
	data := generateTestData(TEST_DATA_LENGTH)
	t.Log("Input data:", data)

	MergeSort(data, 0, TEST_DATA_LENGTH)
	t.Log("Output data:", data)

	if !sort.IsSorted(data) {
		t.Error("MergeSort result is not properly sorted")
	}
}

func TestQuickSort(t *testing.T) {
	data := generateTestData(TEST_DATA_LENGTH)
	t.Log("Input data:", data)

	QuickSort(data, 0, TEST_DATA_LENGTH)
	t.Log("Output data:", data)

	if !sort.IsSorted(data) {
		t.Error("QuickSort result is not properly sorted")
	}
}