Last active
April 7, 2021 18:50
-
-
Save steevehook/56e63d1cdac09c71f1fe504e8eafa4a8 to your computer and use it in GitHub Desktop.
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 main | |
import ( | |
"fmt" | |
"math/rand" | |
"time" | |
) | |
func main() { | |
benchmark(100_000) | |
} | |
// Note: the more elements you are sorting the lower this number should be | |
// the sweet spot is between: 8-20 | |
const insertionSortMaxThreshold = 10 | |
type sortFunc func(a, b int) bool | |
func benchmark(n int) { | |
var A []int | |
for i := 0; i < n; i++ { | |
A = append(A, rand.Intn(n)) | |
} | |
start := time.Now() | |
insertionSortFunc(A, func(a, b int) bool { | |
return a < b | |
}) | |
fmt.Println("elapsed for insertion sort:", time.Now().Sub(start)) | |
start = time.Now() | |
mergeSort(A, func(a, b int) bool { | |
return a < b | |
}) | |
fmt.Println("elapsed for merge sort:", time.Now().Sub(start)) | |
start = time.Now() | |
insertionMergeSort(A, func(a, b int) bool { | |
return a < b | |
}) | |
fmt.Println("elapsed for insertion merge sort:", time.Now().Sub(start)) | |
} | |
// merge merges 2 slices into a single slice, also sorting the resulting slice | |
// Note: to ensure the merge function works correctly the L and R must be sorted | |
func merge(L, R []int, fn sortFunc) []int { | |
A := make([]int, len(L)+len(R)) | |
i, j, k := 0, 0, 0 | |
// compare left & right side elements before merging | |
for i < len(L) && j < len(R) { | |
if fn(L[i], R[j]) { | |
A[k] = L[i] | |
i++ | |
} else { | |
A[k] = R[j] | |
j++ | |
} | |
k++ | |
} | |
// check if any elements from the left/right side | |
// were missed in the comparison section above | |
for i < len(L) { | |
A[k] = L[i] | |
i++ | |
k++ | |
} | |
for j < len(R) { | |
A[k] = R[j] | |
j++ | |
k++ | |
} | |
return A | |
} | |
// sort sorts the given slice by using the Merge Sort algorithm | |
// the algorithm uses the divide & conquer approach by dividing the problem into sub problems | |
// the algorithm works recursively, by calling itself | |
// HOW IT WORKS: | |
// 1. the slice is divided in 2 pieces (right, left) | |
// 2. the right and left sides are sorted first then they are merged | |
// 3. the sort function divides the incoming slice till it cannot be divided anymore (the slice has only 1 element) | |
// 4. after that it starts merging & sorting all the slices back | |
// 5. at the end we have 1 single slice sorted out | |
func sort(A []int, fn sortFunc) []int { | |
if fn == nil { | |
fn = func(a, b int) bool { | |
return a < b | |
} | |
} | |
if len(A) > 1 { | |
m := len(A) / 2 | |
L := A[:m] | |
R := A[m:] | |
// The long version for languages that do not support clever constructs | |
//n1 := len(A) / 2 | |
//n2 := len(A) - n1 | |
//L, R := make([]int, n1), make([]int, n2) | |
//for i := 0; i < n1; i++ { | |
// L[i] = A[i] | |
//} | |
//for j := 0; j < n2; j++ { | |
// R[j] = A[n1+j] | |
//} | |
// sort the right side | |
// sort the left side | |
// merge the sorted sides | |
// do this recursively till the slice has 1 element only | |
A = merge(sort(R, fn), sort(L, fn), fn) | |
} | |
return A | |
} | |
// mergeSort sorts the given slice by using the Merge Sort algorithm | |
// the algorithm uses the divide & conquer approach by dividing the problem into sub problems | |
// the algorithm works recursively, by calling itself | |
// HOW IT WORKS: | |
// 1. the slice is divided in 2 pieces (right, left) | |
// 2. the right and left sides are sorted first then they are merged | |
// 3. the sort function divides the incoming slice till it cannot be divided anymore (the slice has only 1 element) | |
// 4. after that it starts merging & sorting all the slices back | |
// 5. at the end we have 1 single slice sorted out | |
func mergeSort(A []int, fn sortFunc) []int { | |
if fn == nil { | |
fn = func(a, b int) bool { | |
return a < b | |
} | |
} | |
if len(A) > 1 { | |
m := len(A) / 2 | |
L := A[:m] | |
R := A[m:] | |
// The long version for languages that do not support clever constructs | |
//n1 := len(A) / 2 | |
//n2 := len(A) - n1 | |
//L, R := make([]int, n1), make([]int, n2) | |
//for i := 0; i < n1; i++ { | |
// L[i] = A[i] | |
//} | |
//for j := 0; j < n2; j++ { | |
// R[j] = A[n1+j] | |
//} | |
// sort the right side | |
// sort the left side | |
// merge the sorted sides | |
// do this recursively till the slice has 1 element only | |
A = merge(mergeSort(R, fn), mergeSort(L, fn), fn) | |
} | |
return A | |
} | |
// insertionMergeSort uses a combination of insertion & merge sorting algorithms to sort a given slice | |
// it uses the insertion sorting for small data sets | |
// and it uses merge sort till the data set becomes small enough to use insertion sorting | |
func insertionMergeSort(A []int, fn sortFunc) []int { | |
if fn == nil { | |
fn = func(a, b int) bool { | |
return a < b | |
} | |
} | |
if len(A) > 1 { | |
if len(A) <= insertionSortMaxThreshold { | |
return insertionSortFunc(A, fn) | |
} | |
m := len(A) / 2 | |
L := A[:m] | |
R := A[m:] | |
// sort the right side | |
// sort the left side | |
// merge the sorted sides | |
// do this recursively till the slice has a minimum of elements (i.e. 10) | |
//to apply the insertion sorting algorithm | |
A = merge(insertionMergeSort(R, fn), insertionMergeSort(L, fn), fn) | |
} | |
return A | |
} | |
// insertionSortFunc uses the insertion sort algorithm and a sorting function | |
func insertionSortFunc(A []int, fn sortFunc) []int { | |
if fn == nil { | |
fn = func(a, b int) bool { | |
return a < b | |
} | |
} | |
for j := 1; j < len(A); j++ { | |
key := A[j] | |
i := j - 1 | |
for i > -1 && fn(key, A[i]) { | |
A[i+1] = A[i] | |
i -= 1 | |
} | |
A[i+1] = key | |
} | |
return A | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment