Skip to content
{{ message }}

Instantly share code, notes, and snippets.

# jasonrdsouza/sorts.go

Last active Aug 27, 2017
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") } }
to join this conversation on GitHub. Already have an account? Sign in to comment