Last active
August 27, 2017 00:40
-
-
Save jasonrdsouza/aa84c11eee0d8cb1a981 to your computer and use it in GitHub Desktop.
Sorts in Go
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// 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) | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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