Documentation
¶
Overview ¶
Package gosort implements several sorting algorithms and experiments.
Index ¶
- func BitonicSort(nums []int)
- func BitonicSortNaive(nums *[]int)
- func BlockQuickSort1(nums []int)
- func BlockQuickSort2(nums []int)
- func BlockQuickSortControl1(nums []int)
- func BlockQuickSortControl2(nums []int)
- func HeapSort(nums []int)
- func InsertionSort(nums []int)
- func MergeSort1(nums []int)
- func MergeSort2(nums []int)
- func MergeSort3(nums []int)
- func PdqSort1(nums []int)
- func PdqSort2(nums []int)
- func PdqSort3(nums []int)
- func PdqSortIface1(data sort.Interface)
- func QuickSort1(nums []int)
- func QuickSort2(nums []int)
- func QuickSort3(nums []int)
- func QuickSortIface1(data sort.Interface)
- func RadixSort(nums []int)
- func TimSort1(nums []int)
- func TimSort2(nums []int)
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func BitonicSort ¶
func BitonicSort(nums []int)
BitonicSort implements https://www.inf.fh-flensburg.de/lang/algorithmen/sortieren/bitonic/oddn.htm
func BitonicSortNaive ¶
func BitonicSortNaive(nums *[]int)
BitonicSortNaive is my handwritten version of the CLRS bitonic sorting network with goroutines and out-of-place mergesort default ascending the real full sort of regular integers need to take a slice cause of sentinel padding
func BlockQuickSort1 ¶
func BlockQuickSort1(nums []int)
BlockQuickSort1 implements CLRS quicksort with bad pivot and block partitioning [1]
[1]: S. Edelkamp, A. Weiß, "BlockQuicksort: Avoiding Branch Mispredictions in Quicksort" https://pdfs.semanticscholar.org/b24e/f8021811cd4ef0fcc96a770657b664ee5b52.pdf
func BlockQuickSort2 ¶
func BlockQuickSort2(nums []int)
BlockQuickSort2 implements CLRS quicksort with randomized pivot and block partitioning [1]
[1]: S. Edelkamp, A. Weiß, "BlockQuicksort: Avoiding Branch Mispredictions in Quicksort" https://pdfs.semanticscholar.org/b24e/f8021811cd4ef0fcc96a770657b664ee5b52.pdf
func BlockQuickSortControl1 ¶
func BlockQuickSortControl1(nums []int)
BlockQuickSortControl1 is almost identical to BlockQuickSort1 with blocks removed, for fair bench comparisons
func BlockQuickSortControl2 ¶
func BlockQuickSortControl2(nums []int)
BlockQuickSortControl2 is almost identical to BlockQuickSort2 with blocks removed, for fair bench comparisons
func MergeSort2 ¶
func MergeSort2(nums []int)
MergeSort2 is pkg/sort's mergesort
it does insertion sort in blocks and merges the blocks
it looks a _little bit_ like timsort
func MergeSort3 ¶
func MergeSort3(nums []int)
MergeSort3 implements G&T iterative bottom up mergesort
func PdqSort1 ¶
func PdqSort1(nums []int)
PdqSort1 implements CLRS bad pivot quicksort with pdq bad pivot pattern breaking
Bad-pattern busting is copied from the Rust pdqsort implementation, https://docs.rs/pdqsort/0.1.0/src/pdqsort/lib.rs.html#427
func PdqSort2 ¶
func PdqSort2(nums []int)
PdqSort2 modifies pkg/sort's introsort quicksort with pdq bad pivot pattern breaking
func PdqSort3 ¶
func PdqSort3(nums []int)
PdqSort3 implements CLRS randomized pivot quicksort with pdq bad pivot pattern breaking
func PdqSortIface1 ¶
PdqSortIface1 implements CLRS bad pivot quicksort with pdq bad pivot pattern breaking on a sort.Interface
This is to verify the effect of pattern-busting on the killer adversary
func QuickSort1 ¶
func QuickSort1(nums []int)
QuickSort1 implements CLRS quicksort with basic pivot selection
func QuickSort2 ¶
func QuickSort2(nums []int)
QuickSort2 is copied from pkg/sort - looks like introsort
func QuickSort3 ¶
func QuickSort3(nums []int)
QuickSort3 implements CLRS quicksort with randomized pivot selection
func QuickSortIface1 ¶
QuickSortIface1 implements CLRS quicksort with basic pivot selection
using the sorting.Interface
func RadixSort ¶
func RadixSort(nums []int)
RadixSort is based on a radix sort + counting sort for decimal digits from CLRS
func TimSort1 ¶
func TimSort1(nums []int)
TimSort1 is a simplistic implementation of timsort with no galloping
sources: https://github.com/python/cpython/blob/master/Objects/listobject.c https://medium.com/@rylanbauermeister/understanding-timsort-191c758a42f3 https://wiki.c2.com/?TimSort
Types ¶
This section is empty.