C:/knet/include/kNet/Sort.h File Reference

A range of comparison sort algorithms. More...

#include "Clock.h"
#include "SortCmp.h"
#include "Sort.inl"

Include dependency graph for Sort.h:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Namespaces
namespace	kNet
namespace	kNet::sort
	A range of comparison sort algorithms.
Functions
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.
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.
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.
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.
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.
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).
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.
template<typename T , typename CmpFunc >
void	kNet::sort::MergeSort (T *list, int numItems, CmpFunc &cmp)
	Merge sort has constant running time O(n*logn).
template<typename T , typename CmpFunc >
void	kNet::sort::QuickSort (T *list, int numItems, CmpFunc &cmp)
	Quicksort sorts in avg.
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.
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.
template<typename T , typename CmpFunc >
bool	kNet::sort::IsSorted (T *list, int numItems, CmpFunc &cmp)
	This can be used for debugging.

---

Detailed Description

A range of comparison sort algorithms.