casa::GenSort< T > Class Template Reference
[Utilities_internal_classes]

#include <GenSort.h>

List of all members.

---

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 <cite>Template Type Argument Requirements</cite>).

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.

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 &)
	Implement inline member functions.
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.

---

Member Function Documentation

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.

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>

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 uInt casa::GenSort< T >::heapSort	(	T *	,
		uInt	nr,
		Sort::Order	,
		int	options
	)			[static, private]

Sort C-array using heapsort.

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>

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

Implement inline member functions.

Definition at line 527 of file GenSort.h.

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 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 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 >::insSortAsc	(	T *	,
		Int	,
		int	option
	)			[static, private]

Insertion sort in ascending order.

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 >::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 >::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 >::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 >::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.

---

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

• casa/implement/Utilities/GenSort.h

---