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