sort

package

v0.1.5 Latest Latest Go to latest Published: Nov 8, 2018 License: MIT Imports: 2 Imported by: 0

Details

Sort	Best Case	Average Case	Worst Case	Memory	Comment
InsertionSort	N² / 2	N² / 2	N² / 2	1	N exchanges, Suitable for small N
ShellSort	N	?	?	1	Tight code, Subquadratic
MergeSort	NlgN	NlgN	NlgN	N	Stable, NlgN guarantee, Extra memory
MergeSortRec	NlgN	NlgN	NlgN	N	Stable, NlgN guarantee, Extra memory
HeapSort	NlgN	NlgN	NlgN	1	NlgN guarantee
QuickSort	NlgN	2NlnN	N² / 2	clogN	NlgN probabilistic guarantee
QuickSort3Way	N	2NlnN	N² / 2	clogN	Faster in presence of duplicate keys

By running benchmarks, you can compare the performance of these algorithms with each other and also with built-in sort algorithm of go.

This section is empty.

This section is empty.

func HeapSort(a []Generic, compare Compare)

HeapSort implements heap sort algorithm

func InsertionSort(a []Generic, compare Compare)

InsertionSort implements insertion sort algorithm

func MergeSort(a []Generic, compare Compare)

MergeSort implements merge sort algorithm in an iterative manner

func MergeSortRec(a []Generic, compare Compare)

MergeSortRec implements merge sort algorithm in a recursive manner

func QuickSort(a []Generic, compare Compare)

QuickSort implements quick sort algorithm

func QuickSort3Way(a []Generic, compare Compare)

QuickSort3Way implements 3-way quick sort algorithm

func Select(a []Generic, k int, compare Compare) Generic

Select finds the kth smallest item of an array in O(n) time on average

func ShellSort(a []Generic, compare Compare)

ShellSort implements shell sort algorithm

This section is empty.