General in-place sort functions. More...

#include <GenSort.h>

Static Public Member Functions
static uInt	sort (T *, uInt nr, Sort::Order=Sort::Ascending, int options=Sort::QuickSort)
	Sort a C-array containing `nr` `T`-type objects.
static uInt	sort (Array< T > &, Sort::Order=Sort::Ascending, int options=Sort::QuickSort)
	Sort an `Array` of `T`-type objects The sort is done in place.
static uInt	sort (Block< T > &, uInt nr, Sort::Order=Sort::Ascending, int options=Sort::QuickSort)
	Sort `nr` `T`-type objects in the `Block`.
static T	kthLargest (T *data, uInt nr, uInt k)
	Find the k-th largest value.
Static Private Member Functions
static uInt	quickSort (T *, uInt nr, Sort::Order, int options)
	Sort C-array using quicksort.
static uInt	heapSort (T *, uInt nr, Sort::Order, int options)
	Sort C-array using heapsort.
static uInt	insSort (T *, uInt nr, Sort::Order, int options)
	Sort C-array using insertion sort.
static void	swap (T &, T &)
	Swap 2 elements in array.
static void	quickSortAsc (T *, Int)
	Quicksort in ascending order.
static void	quickSortDesc (T *, Int)
	Quicksort in descending order.
static void	heapSortAsc (T *, Int)
	Heapsort in ascending order.
static void	heapSortDesc (T *, Int)
	Heapsort in descending order.
static void	heapAscSiftDown (Int, Int, T *)
	Helper function for ascending heapsort.
static void	heapDescSiftDown (Int, Int, T *)
	Helper function for descending heapsort.
static uInt	insSortAsc (T *, Int, int option)
	Insertion sort in ascending order.
static uInt	insSortDesc (T *, Int, int option)
	Insertion sort in descending order.
static uInt	insSortAscDup (T *, Int)
	Insertion sort in ascending order allowing duplicates.
static uInt	insSortDescDup (T *, Int)
	Insertion sort in descending order allowing duplicates.
static uInt	insSortAscNoDup (T *, Int)
	Insertion sort in ascending order allowing no duplicates.
static uInt	insSortDescNoDup (T *, Int)
	Insertion sort in descending order allowing no duplicates.

Detailed Description

template<class T>
class casa::GenSort< T >

General in-place sort functions.

Intended use:

Internal

Review Status

Reviewed By:: Friso Olnon
Date Reviewed:: 1995/03/16
Test programs:: tGenSort

Synopsis

The static member functions of this templated class are highly optimized sort functions. They do an in-place sort of an array of values. The functions are templated, so they can in principle be used with any data type. However, if used with non-builtin data types, their class must provide certain functions (see Template Type Argument Requirements).

If it is impossible or too expensive to define these functions, the Sort class can be used instead. This sorts indirectly using an index array. Instead of the functions mentioned above it requires a comparison routine.

The GenSort functions can sort:

C-arrays of values;
Arrays of values -- the array can have any shape and the increment can be >1;
Blocks of values -- there is a special function to sort less elements than the size of the Block.

The sort order can be specified in the order field:

Sort::Ascending (default),
Sort::Descending.

A sort algorithm can be given in the options field:

Sort::QuickSort (default): is the fastest. It is about 4-6 times faster than the qsort function on the SUN. No worst case has been found, even not for cases where qsort is terribly slow.
Sort::HeapSort: is about twice as slow as quicksort. It has the advantage that the worst case is always o(n*log(n)), while quicksort can have hypothetical inputs with o(n*n).
Sort::InsSort: is o(n*n) for random inputs. It is, however, the only stable sort (i.e. equal values remain in the original order).

Sort::NoDuplicates in the options field indicates that duplicate values should be removed. Multiple options can be given by or-ing them, e.g. Sort::HeapSort | Sort::NoDuplicates.

All the sort functions return the number of values sorted as their function value; when duplicate values have been removed, the number of unique valuess will be returned.

The class also provides a function to find the k-th largest value in an array of values. This uses a stripped-down version of quicksort and is at least 6 times faster than a full quicksort.

Template Type Argument Requirements (T)

operator= to assign when swapping elements
operator<, operator> and operator== to compare elements
default constructor to allocate a temporary

Definition at line 108 of file GenSort.h.

Member Function Documentation

template<class T >

static void casa::GenSort< T >::heapAscSiftDown	(	Int	,
		Int	,
		T *
	)		`[static, private]`

Helper function for ascending heapsort.

template<class T >

static void casa::GenSort< T >::heapDescSiftDown	(	Int	,
		Int	,
		T *
	)		`[static, private]`

Helper function for descending heapsort.

template<class T >

static uInt casa::GenSort< T >::heapSort	(	T *	,
		uInt	nr,
		Sort::Order	,
		int	options
	)		`[static, private]`

Sort C-array using heapsort.

template<class T >

static void casa::GenSort< T >::heapSortAsc	(	T *	,
		Int
	)		`[static, private]`

Heapsort in ascending order.

template<class T >

static void casa::GenSort< T >::heapSortDesc	(	T *	,
		Int
	)		`[static, private]`

Heapsort in descending order.

template<class T >

static uInt casa::GenSort< T >::insSort	(	T *	,
		uInt	nr,
		Sort::Order	,
		int	options
	)		`[static, private]`

Sort C-array using insertion sort.

template<class T >

static uInt casa::GenSort< T >::insSortAsc	(	T *	,
		Int	,
		int	option
	)		`[static, private]`

Insertion sort in ascending order.

template<class T >

static uInt casa::GenSort< T >::insSortAscDup	(	T *	,
		Int
	)		`[static, private]`

Insertion sort in ascending order allowing duplicates.

This is also used by quicksort for its last steps.

template<class T >

static uInt casa::GenSort< T >::insSortAscNoDup	(	T *	,
		Int
	)		`[static, private]`

Insertion sort in ascending order allowing no duplicates.

This is also used by the other sort algorithms to skip duplicates.

template<class T >

static uInt casa::GenSort< T >::insSortDesc	(	T *	,
		Int	,
		int	option
	)		`[static, private]`

Insertion sort in descending order.

template<class T >

static uInt casa::GenSort< T >::insSortDescDup	(	T *	,
		Int
	)		`[static, private]`

Insertion sort in descending order allowing duplicates.

This is also used by quicksort for its last steps.

template<class T >

static uInt casa::GenSort< T >::insSortDescNoDup	(	T *	,
		Int
	)		`[static, private]`

Insertion sort in descending order allowing no duplicates.

This is also used by the other sort algorithms to skip duplicates.

template<class T >

static T casa::GenSort< T >::kthLargest	(	T *	data,
		uInt	nr,
		uInt	k
	)		`[static]`

Find the k-th largest value.

Note: it does a partial sort, thus the data array gets changed..

template<class T >

static uInt casa::GenSort< T >::quickSort	(	T *	,
		uInt	nr,
		Sort::Order	,
		int	options
	)		`[static, private]`

Sort C-array using quicksort.

template<class T >

static void casa::GenSort< T >::quickSortAsc	(	T *	,
		Int
	)		`[static, private]`

Quicksort in ascending order.

template<class T >

static void casa::GenSort< T >::quickSortDesc	(	T *	,
		Int
	)		`[static, private]`

Quicksort in descending order.

template<class T >

static uInt casa::GenSort< T >::sort	(	T *	,
		uInt	nr,
		Sort::Order	= `Sort::Ascending`,
		int	options = `Sort::QuickSort`
	)		`[static]`

Sort a C-array containing nr T-type objects.

The sort is done in place.

Referenced by casa::GenSort_global_functions_genSortInPlace::genSort().

template<class T >

static uInt casa::GenSort< T >::sort	(	Array< T > &	,
		Sort::Order	= `Sort::Ascending`,
		int	options = `Sort::QuickSort`
	)		`[static]`

Sort an Array of T-type objects The sort is done in place.

template<class T >

static uInt casa::GenSort< T >::sort	(	Block< T > &	,
		uInt	nr,
		Sort::Order	= `Sort::Ascending`,
		int	options = `Sort::QuickSort`
	)		`[static]`

Sort nr T-type objects in the Block.

The sort is done in place.

template<class T >

void casa::GenSort< T >::swap	(	T &	l,
		T &	r
	)		`[inline, static, private]`

Swap 2 elements in array.

Implement inline member functions.

Definition at line 527 of file GenSort.h.

The documentation for this class was generated from the following file:

casacore/casa/Utilities/GenSort.h

Static Public Member Functions

Static Private Member Functions

Detailed Description

template<class T> class casa::GenSort< T >

Intended use:

Review Status

Synopsis

Template Type Argument Requirements (T)

Member Function Documentation

template<class T>
class casa::GenSort< T >