Instantly share code, notes, and snippets.

Embed
What would you like to do?
Sorts in 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)
}
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")
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment