kNet::sort Namespace Reference

A range of comparison sort algorithms. More...

Functions
template<typename T , typename CmpFunc >
void	SelectionSort (T *list, int numItems, CmpFunc &cmp)
	Selection sort is a stable sort that has FIXED running time of ~n^2/2.
template<typename T , typename CmpFunc >
void	PartialSelectionSort (T *list, int numItems, int numItemsToSort, CmpFunc &cmp)
	The same as above, but only partially sorts the list so that the numItemsToSort first items in the list are in order, the rest are unordered.
template<typename T , typename CmpFunc >
void	InsertionSort (T *list, int numItems, CmpFunc &cmp)
	Insertion sort is efficent on data that is almost sorted.
template<typename T , typename CmpFunc >
void	ShellSort (T *list, int numItems, CmpFunc &cmp)
	Shell sort is an optimization of insertion sort, performs in O(n^1.25) on average.
template<typename T , typename CmpFunc >
void	BubbleSort (T *list, int numItems, CmpFunc &cmp)
	Bubble sort sorts in worst case O(n^2) time, best case O(n) if the list is already almost sorted.
template<typename T , typename CmpFunc >
void	CocktailSort (T *list, int numItems, CmpFunc &cmp)
	Cocktail sort == Bidirectional Bubble sort == Shaker sort == Ripple sort == Shuttle sort: Stable optimization of Bubble sort, worst case O(n^2).
template<typename T , typename CmpFunc >
void	CombSort (T *list, int numItems, CmpFunc &cmp)
	Comb sort is a "diminishing" Bubble sort, an unstable optimization of Bubble sort.
template<typename T , typename CmpFunc >
void	MergeSort (T *list, int numItems, CmpFunc &cmp)
	Merge sort has constant running time O(n*logn).
template<typename T , typename CmpFunc >
void	QuickSort (T *list, int numItems, CmpFunc &cmp)
	Quicksort sorts in avg.
template<typename T , typename CmpFunc >
void	HeapSort (T *list, int numItems, CmpFunc &cmp)
	Heapsort is an in-place working algorithm that runs in O(n*logn) time.
template<typename T , typename CmpFunc >
void	IntroSort (T *list, int numItems, int nMaxRecursionLevels, CmpFunc &cmp)
	Introspective sort starts as Quicksort, but switches to Heapsort when the maximum number of recursion levels has been exceeded.
template<typename T , typename CmpFunc >
bool	IsSorted (T *list, int numItems, CmpFunc &cmp)
	This can be used for debugging.

---

Detailed Description

A range of comparison sort algorithms.

When to use one of these sorts and when to use the std sorts? (std::sort, std::stable_sort, std::list::sort etc.)

1) Always consider using the standard versions first. For example, the visual c++ std::sort is on average faster than the introsort described here. Additionally, your code has the advantage of being more portable.

2) The sorting algorithms described here operate only on contiguous data. This means that they can only be used to sort vectors and arrays. If you have a linked list, you can only use list::sort. Additionally, the data type T must be assignable.

3) If the std:: sorting performance is not acceptable, figure out the "profile" of your sortable data. Is it in random or mostly sorted order? Is it sorted once, occasionally or on a per-frame basis? Are all items unique or are there several that are equivalent? Is stable sort-property required? Then look at the actual implementations of these algorithms and decide what fits the data profile the best. And of course, always measure the actual performance.

Note that a few of these algorithms have only been implemented as a curiosity. Selection sort for example just plain sucks.

The client-implemented comparison function must be of this form:

template<typename T> int CmpFunc(const T &a, const T &b);

Parameters:

	a	The first comparison operand.
	b	The second comparison operand.

Returns:

a negative value if a < b, 0 if a == b and a positive value when b < a.

---

Function Documentation

template<typename T , typename CmpFunc >

void kNet::sort::SelectionSort	(	T *	list,
		int	numItems,
		CmpFunc &	cmp
	)

Selection sort is a stable sort that has FIXED running time of ~n^2/2.

It can contend only against Bubble sort, which in general performs far better. The only advantage of this against other sorts is that CmpFunc can be a partial ordering instead of a total ordering (For other sort functions, cmp must be a total order).

template<typename T , typename CmpFunc >

void kNet::sort::PartialSelectionSort	(	T *	list,
		int	numItems,
		int	numItemsToSort,
		CmpFunc &	cmp
	)

The same as above, but only partially sorts the list so that the numItemsToSort first items in the list are in order, the rest are unordered.

Gives a slight performance boost when only a part of the list needs to get ordered. Doesn't affect the asymptotics though, which is O(k*n), where k=numItemsToSort.

template<typename T , typename CmpFunc >

void kNet::sort::InsertionSort	(	T *	list,
		int	numItems,
		CmpFunc &	cmp
	)

Insertion sort is efficent on data that is almost sorted.

Worst case O(n^2), avg. n^2/4, Best case O(n). This sort is stable.

template<typename T , typename CmpFunc >

void kNet::sort::ShellSort	(	T *	list,
		int	numItems,
		CmpFunc &	cmp
	)

Shell sort is an optimization of insertion sort, performs in O(n^1.25) on average.

Worst case O(n^2). This sort is not stable.

template<typename T , typename CmpFunc >

void kNet::sort::BubbleSort	(	T *	list,
		int	numItems,
		CmpFunc &	cmp
	)

Bubble sort sorts in worst case O(n^2) time, best case O(n) if the list is already almost sorted.

This sort is stable.

template<typename T , typename CmpFunc >

void kNet::sort::CocktailSort	(	T *	list,
		int	numItems,
		CmpFunc &	cmp
	)

Cocktail sort == Bidirectional Bubble sort == Shaker sort == Ripple sort == Shuttle sort: Stable optimization of Bubble sort, worst case O(n^2).

Works by alternating the bubble directions in bubble sort.

If the list is mostly ordered, then the running time is near O(n).

template<typename T , typename CmpFunc >

void kNet::sort::CombSort	(	T *	list,
		int	numItems,
		CmpFunc &	cmp
	)

Comb sort is a "diminishing" Bubble sort, an unstable optimization of Bubble sort.

Generally performs far better than Bubble/Cocktail sorts.

template<typename T , typename CmpFunc >

void kNet::sort::MergeSort	(	T *	list,
		int	numItems,
		CmpFunc &	cmp
	)

Merge sort has constant running time O(n*logn).

Requires O(n) of additional space and has a recursive call overhead of 2n-1. This sort is stable. Note that this sort dynamically allocates memory with a call to new[].

template<typename T , typename CmpFunc >

void kNet::sort::QuickSort	(	T *	list,
		int	numItems,
		CmpFunc &	cmp
	)

Quicksort sorts in avg.

On the development computer overflows the stack if numItems is larger than ~57000 and the list is already sorted.

O(n*logn) time, with a O(logn) recursive call overhead. In worst case (array is sorted in descending order) degenerates into a selection sort with O(n^2) complexity. The middle element of the sublist is chosen as pivot. This sort is not stable, and it has a potential security vulnerability due to recursive calls.

template<typename T , typename CmpFunc >

void kNet::sort::HeapSort	(	T *	list,
		int	numItems,
		CmpFunc &	cmp
	)

Heapsort is an in-place working algorithm that runs in O(n*logn) time.

Generally slower than Quicksort, but is better in worst case scenario when the list is almost sorted. This sort is not stable.

Referenced by IntroSort().

template<typename T , typename CmpFunc >

void kNet::sort::IntroSort	(	T *	list,
		int	numItems,
		int	nMaxRecursionLevels,
		CmpFunc &	cmp
	)

Introspective sort starts as Quicksort, but switches to Heapsort when the maximum number of recursion levels has been exceeded.

This shields the implementation against stack overflow. If it's known that Introsorting a particular list will cause it to switch to Heapsort, it is faster to directly call Heapsort instead. Introsort is not stable.

References HeapSort().