GenSort.h

Classes

GenSort -- General in-place sort functions (full description)
GenSortIndirect -- General indirect sort functions (full description)
Global Functions -- Global in-place sort functions (full description)
Global Functions -- Global indirect sort functions (full description)

template<class T> class GenSort

Interface

Public Members
static uInt sort (T*, uInt nr, Sort::Order = Sort::Ascending, int options = Sort::QuickSort)
static uInt sort (Array<T>&, Sort::Order = Sort::Ascending, int options = Sort::QuickSort)
static uInt sort (Block<T>&, uInt nr, Sort::Order = Sort::Ascending, int options = Sort::QuickSort)
static T kthLargest (T* data, uInt nr, uInt k)
Private Members
static uInt quickSort (T*, uInt nr, Sort::Order, int options)
static uInt heapSort (T*, uInt nr, Sort::Order, int options)
static uInt insSort (T*, uInt nr, Sort::Order, int options)
static inline void swap (T&, T&)
static void quickSortAsc (T*, Int)
static void quickSortDesc (T*, Int)
static void heapSortAsc (T*, Int)
static void heapSortDesc (T*, Int)
static void heapAscSiftDown (Int, Int, T*)
static void heapDescSiftDown (Int, Int, T*)
static uInt insSortAsc (T*, Int, int option)
static uInt insSortDesc (T*, Int, int option)
static uInt insSortAscDup (T*, Int)
static uInt insSortDescDup (T*, Int)
static uInt insSortAscNoDup (T*, Int)
static uInt insSortDescNoDup (T*, Int)

Description

Review Status

Reviewed By:
Friso Olnon
Date Reviewed:
1995/03/16
Programs:
Tests:

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:

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)

Member Description

static uInt sort (T*, uInt nr, Sort::Order = Sort::Ascending, int options = Sort::QuickSort)

Sort a C-array containing nr T-type objects. The sort is done in place.

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. The sort is done in place.

static T kthLargest (T* data, uInt nr, uInt k)

Find the k-th largest value. Note: it does a partial sort, thus the data array gets changed..

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 inline 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. This is also used by quicksort for its last steps.

static uInt insSortDescDup (T*, Int)

Insertion sort in descending order allowing duplicates. This is also used by quicksort for its last steps.

static uInt insSortAscNoDup (T*, Int)

Insertion sort in ascending order allowing no duplicates. This is also used by the other sort algorithms to skip duplicates.

static uInt insSortDescNoDup (T*, Int)

Insertion sort in descending order allowing no duplicates. This is also used by the other sort algorithms to skip duplicates.

template<class T> class GenSortIndirect

Interface

Public Members
static uInt sort (Vector<uInt>& indexVector, const T* data, uInt nr, Sort::Order = Sort::Ascending, int options = Sort::QuickSort)
static uInt sort (Vector<uInt>& indexVector, const Array<T>& data, Sort::Order = Sort::Ascending, int options = Sort::QuickSort)
static uInt sort (Vector<uInt>& indexVector, const Block<T>& data, uInt nr, Sort::Order = Sort::Ascending, int options = Sort::QuickSort)
Private Members
static uInt quickSort (uInt* inx, const T* data, uInt nr, Sort::Order, int options)
static uInt heapSort (uInt* inx, const T* data, uInt nr, Sort::Order, int options)
static uInt insSort (uInt* inx, const T* data, uInt nr, Sort::Order, int options)
static inline void swapInx (uInt& index1, uInt& index2)
static inline int isAscending (const T* data, Int index1, Int index2)
static inline int isDescending (const T*, Int index1, Int index2)
static void quickSortAsc (uInt* inx, const T*, Int nr)
static void quickSortDesc (uInt* inx, const T*, Int nr)
static void heapSortAsc (uInt* inx, const T*, Int nr)
static void heapSortDesc (uInt* inx, const T*, Int nr)
static void heapAscSiftDown (uInt* inx, Int, Int, const T*)
static void heapDescSiftDown (uInt* inx, Int, Int, const T*)
static uInt insSortAsc (uInt* inx, const T*, Int nr, int option)
static uInt insSortDesc (uInt* inx, const T*, Int nr, int option)
static uInt insSortAscDup (uInt* inx, const T*, Int nr)
static uInt insSortDescDup (uInt* inx, const T*, Int nr)
static uInt insSortAscNoDup (uInt* inx, const T*, Int nr)
static uInt insSortDescNoDup (uInt* inx, const T*, Int nr)

Description

Synopsis

This class is similar to GenSort. The only difference is that the functions in this class sort indirectly instead of in-place. They return the result of the sort as an sorted vector of indices This is slower, because an extra indirection is involved in each comparison. However, this sort allows to sort const data. Another advantage is that this sort is always stable (i.e. equal values are kept in their original order).

Member Description

static uInt sort (Vector<uInt>& indexVector, const T* data, uInt nr, Sort::Order = Sort::Ascending, int options = Sort::QuickSort)

Sort a C-array containing nr T-type objects. The resulting index vector gives the sorted indices.

static uInt sort (Vector<uInt>& indexVector, const Array<T>& data, Sort::Order = Sort::Ascending, int options = Sort::QuickSort)

Sort a C-array containing nr T-type objects. The resulting index vector gives the sorted indices.

static uInt sort (Vector<uInt>& indexVector, const Block<T>& data, uInt nr, Sort::Order = Sort::Ascending, int options = Sort::QuickSort)

Sort a C-array containing nr T-type objects. The resulting index vector gives the sorted indices.

static uInt quickSort (uInt* inx, const T* data, uInt nr, Sort::Order, int options)

Sort container using quicksort.

static uInt heapSort (uInt* inx, const T* data, uInt nr, Sort::Order, int options)

Sort container using heapsort.

static uInt insSort (uInt* inx, const T* data, uInt nr, Sort::Order, int options)

Sort container using insertion sort.

static inline void swapInx (uInt& index1, uInt& index2)

Swap 2 indices.

static inline int isAscending (const T* data, Int index1, Int index2)

Check if 2 values are in ascending order. When equal, the order is correct if index1static inline int isDescending (const T*, Int index1, Int index2)

Check if 2 values are in descending order. When equal, the order is correct if index1static void quickSortAsc (uInt* inx, const T*, Int nr)

Quicksort in ascending order.

static void quickSortDesc (uInt* inx, const T*, Int nr)

Quicksort in descending order.

static void heapSortAsc (uInt* inx, const T*, Int nr)

Heapsort in ascending order.

static void heapSortDesc (uInt* inx, const T*, Int nr)

Heapsort in descending order.

static void heapAscSiftDown (uInt* inx, Int, Int, const T*)

Helper function for ascending heapsort.

static void heapDescSiftDown (uInt* inx, Int, Int, const T*)

Helper function for descending heapsort.

static uInt insSortAsc (uInt* inx, const T*, Int nr, int option)

Insertion sort in ascending order.

static uInt insSortDesc (uInt* inx, const T*, Int nr, int option)

Insertion sort in descending order.

static uInt insSortAscDup (uInt* inx, const T*, Int nr)

Insertion sort in ascending order allowing duplicates. This is also used by quicksort for its last steps.

static uInt insSortDescDup (uInt* inx, const T*, Int nr)

Insertion sort in descending order allowing duplicates. This is also used by quicksort for its last steps.

static uInt insSortAscNoDup (uInt* inx, const T*, Int nr)

Insertion sort in ascending order allowing no duplicates. This is also used by the other sort algorithms to skip duplicates.

static uInt insSortDescNoDup (uInt* inx, const T*, Int nr)

Insertion sort in descending order allowing no duplicates. This is also used by the other sort algorithms to skip duplicates.

Global in-place sort functions (source)

Interface

inlineuInt genSort (T* data, uInt nr)
inlineuInt genSort (Array<T>& data)
inlineuInt genSort (Block<T>& data)
inlineuInt genSort (Block<T>& data, uInt nr)
inlineuInt genSort (T* data, uInt nr, int options)
inlineuInt genSort (Array<T>& data, int options)
inlineuInt genSort (Block<T>& data, int options)
inlineuInt genSort (Block<T>& data, uInt nr, int options)
inlineuInt genSort (T* data, uInt nr, Sort::Order order)
inlineuInt genSort (Array<T>& data, Sort::Order order)
inlineuInt genSort (Block<T>& data, Sort::Order order)
inlineuInt genSort (Block<T>& data, uInt nr, Sort::Order order)
inlineuInt genSort (T* data, uInt nr, Sort::Order order, int options)
inlineuInt genSort (Array<T>& data, Sort::Order order, int options)
inlineuInt genSort (Block<T>& data, Sort::Order order, int options)
inlineuInt genSort (Block<T>& data, uInt nr, Sort::Order order, int options)

Description

The following global functions are easier to use than the static GenSort member functions. They do an in-place sort of data, thus the data themselves are moved ending up in the requested order.

The default sorting method is QuickSort, which is the fastest. However, there are pathological cases where it can be slow. HeapSort is about twice a slow, but its speed is guaranteed. InsSort (insertion sort) can be very, very slow, but it is the only stable sort method (i.e. equal values are kept in their original order). However, indirect sorting methods are available to make QuickSort and HeapSort stable.

All sort methods have an option to skip duplicate values. This is the only case where the returned number of values can be less than the original number of values.

Member Description

inlineuInt genSort (T* data, uInt nr)
inlineuInt genSort (Array<T>& data)
inlineuInt genSort (Block<T>& data)
inlineuInt genSort (Block<T>& data, uInt nr)

In-place sort in ascending order using QuickSort.

inlineuInt genSort (T* data, uInt nr, int options)
inlineuInt genSort (Array<T>& data, int options)
inlineuInt genSort (Block<T>& data, int options)
inlineuInt genSort (Block<T>& data, uInt nr, int options)

In-place sort in ascending order using given option. This option gives the sort method (Sort::QuickSort, Sort::HeapSort or Sort::InsSort) and/or the option Sort::NoDuplicates.

inlineuInt genSort (T* data, uInt nr, Sort::Order order)
inlineuInt genSort (Array<T>& data, Sort::Order order)
inlineuInt genSort (Block<T>& data, Sort::Order order)
inlineuInt genSort (Block<T>& data, uInt nr, Sort::Order order)

In-place sort in given order using QuickSort. The order must be Sort::Ascending or Sort::Descending.

inlineuInt genSort (T* data, uInt nr, Sort::Order order, int options)
inlineuInt genSort (Array<T>& data, Sort::Order order, int options)
inlineuInt genSort (Block<T>& data, Sort::Order order, int options)
inlineuInt genSort (Block<T>& data, uInt nr, Sort::Order order, int options)

In-place sort in given order using given option. This option gives the sort method (Sort::QuickSort, Sort::HeapSort, or Sort::InsSort) and/or the option Sort::NoDuplicates. The order must be Sort::Ascending or Sort::Descending.

Global indirect sort functions (source)

Interface

inlineuInt genSort (Vector<uInt>& indexVector, const T* data, uInt nr)
inlineuInt genSort (Vector<uInt>& indexVector, const Array<T>& data)
inlineuInt genSort (Vector<uInt>& indexVector, const Block<T>& data)
inlineuInt genSort (Vector<uInt>& indexVector, const Block<T>& data, uInt nr)
inlineuInt genSort (Vector<uInt>& indexVector, const T* data, uInt nr, int options)
inlineuInt genSort (Vector<uInt>& indexVector, const Array<T>& data, int options)
inlineuInt genSort (Vector<uInt>& indexVector, const Block<T>& data, int options)
inlineuInt genSort (Vector<uInt>& indexVector, const Block<T>& data, uInt nr, int options)
inlineuInt genSort (Vector<uInt>& indexVector, const T* data, uInt nr, Sort::Order order)
inlineuInt genSort (Vector<uInt>& indexVector, const Array<T>& data, Sort::Order order)
inlineuInt genSort (Vector<uInt>& indexVector, const Block<T>& data, Sort::Order order)
inlineuInt genSort (Vector<uInt>& indexVector, const Block<T>& data, uInt nr, Sort::Order order)
inlineuInt genSort (Vector<uInt>& indexVector, const T* data, uInt nr, Sort::Order order, int options)
inlineuInt genSort (Vector<uInt>& indexVector, Array<T>& data, Sort::Order order, int options)
inlineuInt genSort (Vector<uInt>& indexVector, const Block<T>& data, Sort::Order order, int options)
inlineuInt genSort (Vector<uInt>& indexVector, const Block<T>& data, uInt nr, Sort::Order order, int options)

Description

The following global functions easier to use than the static GenSortIndirect member functions. They do an indirect sort of data, thus the data themselves are not moved. Rather an index vector is returned giving the sorted data indices.

The default sorting method is QuickSort, which is the fastest. However, there are pathological cases where it can be slow. HeapSort is about twice a slow, but its speed is guaranteed. InsSort (insertion sort) can be very, very slow.

Unlike the in-place sorting methods , all indirect sorting methods are stable (i.e. equal values are left in their original order).

All sort methods have an option to skip duplicate values. This is the only case where the returned number of values can be less than the original number of values.

Member Description

inlineuInt genSort (Vector<uInt>& indexVector, const T* data, uInt nr)
inlineuInt genSort (Vector<uInt>& indexVector, const Array<T>& data)
inlineuInt genSort (Vector<uInt>& indexVector, const Block<T>& data)
inlineuInt genSort (Vector<uInt>& indexVector, const Block<T>& data, uInt nr)

Indirect sort in ascending order using QuickSort.

inlineuInt genSort (Vector<uInt>& indexVector, const T* data, uInt nr, int options)
inlineuInt genSort (Vector<uInt>& indexVector, const Array<T>& data, int options)
inlineuInt genSort (Vector<uInt>& indexVector, const Block<T>& data, int options)
inlineuInt genSort (Vector<uInt>& indexVector, const Block<T>& data, uInt nr, int options)

Indirect sort in ascending order using given option. This option gives the sort method (Sort::QuickSort, Sort::HeapSort, or Sort::InsSort) and/or the option Sort::NoDuplicates.

inlineuInt genSort (Vector<uInt>& indexVector, const T* data, uInt nr, Sort::Order order)
inlineuInt genSort (Vector<uInt>& indexVector, const Array<T>& data, Sort::Order order)
inlineuInt genSort (Vector<uInt>& indexVector, const Block<T>& data, Sort::Order order)
inlineuInt genSort (Vector<uInt>& indexVector, const Block<T>& data, uInt nr, Sort::Order order)

Indirect sort in given order using QuickSort. The order must be Sort::Ascending or Sort::Descending.

inlineuInt genSort (Vector<uInt>& indexVector, const T* data, uInt nr, Sort::Order order, int options)
inlineuInt genSort (Vector<uInt>& indexVector, Array<T>& data, Sort::Order order, int options)
inlineuInt genSort (Vector<uInt>& indexVector, const Block<T>& data, Sort::Order order, int options)
inlineuInt genSort (Vector<uInt>& indexVector, const Block<T>& data, uInt nr, Sort::Order order, int options)

Indirect sort in given order using given option. This option gives the sort method (Sort::QuickSort, Sort::HeapSort, or Sort::InsSort) and/or the option Sort::NoDuplicates. The order must be Sort::Ascending or Sort::Descending.