Main Page | Namespace List | Class Hierarchy | Alphabetical List | Class List | File List | Namespace Members | Class Members | File Members | Related Pages

/ray/src/lib/tl/sort.h File Reference

Array sorting templates. More...

#include <lib/sconfig.h>
#include <lib/tl/defop.h>

Include dependency graph for sort.h:

Include dependency graph

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

Included by dependency graph

Go to the source code of this file.

Defines

#define _TemplateLibrary_SORT_H_   1
#define TLIB_QUICKSORT_TAIL_CALL_OPTIMIZE   1
 Internally used by QuickSort().


Functions

template<typename T, typename _OP> void _SortSwap (T *a, size_t i0, size_t i1, T &tmp, const _OP &op)
 Swap indices i0 and i1 in a[] using tmp as a temporary.

template<typename T, typename _OP> void InsertionSortBS (T *a, size_t nelem, const _OP &op=TLDefaultOperators_CDT< T >())
 Insertion sort template.

template<typename T, typename _OP> void InsertionSort (T *a, size_t nelem, const _OP &op=TLDefaultOperators_CDT< T >())
 Insertion sort template.

template<typename T, typename _OP> void HeapSort (T *_a, size_t nelem, const _OP &op=TLDefaultOperators_CDT< T >())
 Heap sort template.

template<typename T, typename _OP> void _QuickSort_Final (T *a, size_t nelem, T &tmp, const _OP &op)
 Internally used by DumbQuickSort() and CleverQuickSort().

template<typename T, typename _OP> void _DumbQuickSort_R (T *a, size_t nelem, size_t insertion_sort_thresh, const _OP &op)
 Internally used by DumbQuickSort().

template<typename T, typename _OP> void DumbQuickSort (T *a, size_t nelem, size_t insertion_sort_thresh=16, const _OP &op=TLDefaultOperators_CDT< T >())
 Quick sort template.

template<typename T, typename _OP> void _CleverQuickSort_R (T *a, size_t nelem, size_t insertion_sort_thresh, const _OP &op)
template<typename T, typename _OP> void CleverQuickSort (T *a, size_t nelem, size_t insertion_sort_thresh=16, const _OP &op=TLDefaultOperators_CDT< T >())
 Quick sort template.

Detailed Description

Array sorting templates.

Author:
Wolfgang Wieser ] wwieser (a) gmx <*> de [

Definition in file sort.h.

Define Documentation

#define _TemplateLibrary_SORT_H_   1
 

Definition at line 18 of file sort.h.

#define TLIB_QUICKSORT_TAIL_CALL_OPTIMIZE   1
 

Internally used by QuickSort().

For internal use only.

Recursive "clever" quicksort main routine (using median-of-3); do not use directly. Memory consumption is O(log(n)) worst case as the larger subarray is handeled using explicit tail recursion optimization (can be switched on/off using TLIB_QUICKSORT_TAIL_CALL_OPTIMIZE).

Definition at line 322 of file sort.h.

Function Documentation

template<typename T, typename _OP>
void _CleverQuickSort_R (  T *  a,
size_t  nelem,
size_t  insertion_sort_thresh,
const _OP &  op
) 
 

Definition at line 323 of file sort.h.

References _QuickSort_Final(), _SortSwap(), and Assert.

Referenced by CleverQuickSort().

template<typename T, typename _OP>
void _DumbQuickSort_R (  T *  a,
size_t  nelem,
size_t  insertion_sort_thresh,
const _OP &  op
) 
 

Internally used by DumbQuickSort().

For internal use only.

Recursive (standard/dumb) quicksort main routine; do not use directly.

Definition at line 242 of file sort.h.

References _QuickSort_Final(), _SortSwap(), and Assert.

Referenced by DumbQuickSort().

template<typename T, typename _OP>
void _QuickSort_Final (  T *  a,
size_t  nelem,
T &  tmp,
const _OP &  op
)  [inline]
 

Internally used by DumbQuickSort() and CleverQuickSort().

For internal use only.

Does the last non-recursive step in sorting.

Definition at line 216 of file sort.h.

References _SortSwap(), and InsertionSort().

Referenced by _CleverQuickSort_R(), and _DumbQuickSort_R().

template<typename T, typename _OP>
void _SortSwap (  T *  a,
size_t  i0,
size_t  i1,
T &  tmp,
const _OP &  op
)  [inline]
 

Swap indices i0 and i1 in a[] using tmp as a temporary.

For internal use only.

Definition at line 35 of file sort.h.

Referenced by _CleverQuickSort_R(), _DumbQuickSort_R(), _QuickSort_Final(), HeapSort(), and InsertionSortBS().

template<typename T, typename _OP>
void CleverQuickSort (  T *  a,
size_t  nelem,
size_t  insertion_sort_thresh = 16,
const _OP &  op = TLDefaultOperators_CDT<T>()
) 
 

Quick sort template.

Author:
Wolfgang Wieser ] wwieser (a) gmx <*> de [
Implements "clever" quick sort with median-of-3 key selection and an insertion sort step for small subarrays (size < insertion_sort_thresh). Good values for the threshold are in range 8 and 16. Furthermore, it implements explicit tail recursion optimization for the larger one of both the subarrays resulting in O(log(n)) worst case memory comsumption (in contrast to O(n^2) (worst) using the pure recursive version).

Do not use on nearly sorted data because this is a dangerous case for quicksort. Instead, use smoothsort or insertion sort in this case.

Todo:
Possible improvement for clever quick sort: introsort: use heapsort when runtime becomes quadratic (i.e. recursion depth >> log(nelem)).
Sort order is ascenting.

Runtime: O(n*log(n)) average case and O(n^2) worst case.
Memory consumption: O(log(n)) average and worst case.
Stable: NO.

Definition at line 462 of file sort.h.

References _CleverQuickSort_R().

Referenced by X_CleverQuickSort().

template<typename T, typename _OP>
void DumbQuickSort (  T *  a,
size_t  nelem,
size_t  insertion_sort_thresh = 16,
const _OP &  op = TLDefaultOperators_CDT<T>()
) 
 

Quick sort template.

Author:
Wolfgang Wieser ] wwieser (a) gmx <*> de [
Implements (standard dumb) quick sort with an insertion sort step for small subarrays (size < insertion_sort_thresh). Do not use on nearly sorted data because this is the worst case for (dumb) quick sort.

Sort order is ascenting.

Runtime: O(n*log(n)) average case and O(n^2) worst case.
Memory consumption: O(log(n)) average case, O(n^2) worst case.
Stable: NO.

Definition at line 301 of file sort.h.

References _DumbQuickSort_R().

Referenced by X_DumbQuickSort().

template<typename T, typename _OP>
void HeapSort (  T *  _a,
size_t  nelem,
const _OP &  op = TLDefaultOperators_CDT<T>()
) 
 

Heap sort template.

Author:
Wolfgang Wieser ] wwieser (a) gmx <*> de [
Implements bottom-up heap sort. The advantage of heap sort compared to quick sort is that the worst case runtime is O(n*log(n)) (compared to O(n^2) for quick sort) and that only 1 element of additional memory is required (compared to O(log(n)) for clever quick sort).

Unfortunately, heap sort in the average case is slower than quick sort for several reasons; for example heap sort requires efficient random access to the array elements while quick sort is more local and predictive interfering better with CPU caches. Also, the number of compares and assignments in heap sort is larger than for quick sort in the average case.

Do not use on nearly-sorted arrays; for nearly sorted arrays, a heap-sort derived algorithm called smoothsort (Dijkstra) exists, which has O(n) runtime for sorted arrays and a smooth transition to O(n*log(n)) worst case.

Sort order is ascenting.

Runtime: O(n*log(n)) average and worst case.
Memory consumption: One additional element.
Stable: NO.

Definition at line 147 of file sort.h.

References _SortSwap().

Referenced by VM::VMLinker::_MergeNamespaceInfo_Recursive(), and main().

template<typename T, typename _OP>
void InsertionSort (  T *  a,
size_t  nelem,
const _OP &  op = TLDefaultOperators_CDT<T>()
) 
 

Insertion sort template.

Author:
Wolfgang Wieser ] wwieser (a) gmx <*> de [
Implements insertion sort without binary search for insert index.
Use this for nearly sorted data, where elements need to be moved a short distance, e.g. as a "last step" with pre-sorting using quicksort.

Sort order is ascenting.

Runtime: O(n^2) for arbitrary arrays; compares and swaps.
For nearly sorted arrays, avg. move distance m<<n: O(n*m) runtime (compares and swaps).
Stable: YES.

Definition at line 97 of file sort.h.

Referenced by VM::VMLinker::_MergeNamespaceInfo_Recursive(), _QuickSort_Final(), and main().

template<typename T, typename _OP>
void InsertionSortBS (  T *  a,
size_t  nelem,
const _OP &  op = TLDefaultOperators_CDT<T>()
) 
 

Insertion sort template.

Author:
Wolfgang Wieser ] wwieser (a) gmx <*> de [
Implements insertion sort with binary search for insert index.
Use this for nearly sorted data, i.e. arrays where a few elements are out of order and these few are to be moved a long distance.

Sort order is ascenting.

Runtime: O(n^2) for arbitrary arrays: O(n*log(n)) compares and O(n^2) swaps.
For nearly sorted arrays (m<<n non-sorted elements): O(n*m) runtime: O(m*log(n)) compares and O(m*n) swaps.
Stable: YES.

Definition at line 59 of file sort.h.

References _SortSwap().

Referenced by main().

Generated on Sat Feb 19 22:34:52 2005 for Ray by doxygen 1.3.5