Loading...
Searching...
No Matches
casacore::GenSort< T > Class Template Reference
casa package (libcasa_casa) » Utilities_module » Utilities_module_internal_classes

More...

`#include <GenSort.h>`

## Static Public Member Functions

static uInt | sort (T *, uInt nr, Sort::Order=Sort::Ascending, int options=0)
| Sort a C-array containing nr T-type objects.
static uInt | sort (Array< T > &, Sort::Order=Sort::Ascending, int options=0)
static uInt | sort (Block< T > &, uInt nr, Sort::Order=Sort::Ascending, int options=0)
static T | kthLargest (T *data, uInt nr, uInt k)
| Find the k-th largest value.
static uInt | quickSort (T *, uInt nr, Sort::Order=Sort::Ascending, int options=0)
| Sort C-array using quicksort.
static uInt | heapSort (T *, uInt nr, Sort::Order=Sort::Ascending, int options=0)
| Sort C-array using heapsort.
static uInt | insSort (T *, uInt nr, Sort::Order=Sort::Ascending, int options=0)
| Sort C-array using insertion sort.
static uInt | parSort (T *, uInt nr, Sort::Order=Sort::Ascending, int options=0, int nthread=0)
| Sort C-array using parallel merge sort (using OpenMP).
static void | swap (T &, T &)
| Swap 2 elements in array.
static void | reverse (T *data, const T *res, uInt nrrec)
| Reverse the elements in res and put them into data.

## Static Private Member Functions

static T * | merge (T *data, T *tmp, uInt nrrec, uInt *index, uInt nparts)
| Thedata buffer is divided in nparts parts.
static void | quickSortAsc (T *, Int, Bool multiThread=False, Int rec_lim=128)
| Quicksort in ascending order.
static void | heapSortAsc (T *, Int)
| Heapsort in ascending order.
static void | heapAscSiftDown (Int, Int, T *)
| Helper function for ascending heapsort.
static uInt | insSortAsc (T *, Int, int option)
| Insertion sort in ascending order.
static uInt | insSortAscDup (T *, Int)
| Insertion sort in ascending order allowing duplicates.
static uInt | insSortAscNoDup (T *, Int)
| Insertion sort in ascending order allowing no duplicates.

## Detailed Description

template<class T>
class casacore::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.

Previously the sort algorithm to use could 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).

However, these options are not used anymore because the sort now always uses a merge sort that is equally fast for random input and much faster for degenerated cases like an already ordered or reversely ordered array. Furthermore, merge sort is always stable and will be parallelized if OpenMP support is enabled giving a 6-fold speedup on 8 cores.
Sort::NoDuplicates in the options field indicates that duplicate values will be removed (only the first occurrance is kept).
The previous sort functionality is still available through the functions quickSort, heapSort, and insSort.

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 111 of file GenSort.h.

## Member Function Documentation

## heapAscSiftDown()

template<class T>

void casacore::GenSort< T >::heapAscSiftDown | ( | Int | ,
|  | Int | ,
|  | T * | )

static private

Helper function for ascending heapsort.

## heapSort()

template<class T>

uInt casacore::GenSort< T >::heapSort | ( | T * | ,
|  | uInt | nr,
|  | Sort::Order | = Sort::Ascending,
|  | int | options = 0 )

static

Sort C-array using heapsort.

References casacore::Sort::Ascending.

## heapSortAsc()

template<class T>

void casacore::GenSort< T >::heapSortAsc | ( | T * | ,
|  | Int | )

static private

Heapsort in ascending order.

## insSort()

template<class T>

uInt casacore::GenSort< T >::insSort | ( | T * | ,
|  | uInt | nr,
|  | Sort::Order | = Sort::Ascending,
|  | int | options = 0 )

static

Sort C-array using insertion sort.

References casacore::Sort::Ascending.

## insSortAsc()

template<class T>

uInt casacore::GenSort< T >::insSortAsc | ( | T * | ,
|  | Int | ,
|  | int | option )

static private

Insertion sort in ascending order.

## insSortAscDup()

template<class T>

uInt casacore::GenSort< T >::insSortAscDup | ( | T * | ,
|  | Int | )

static private

Insertion sort in ascending order allowing duplicates.

This is also used by quicksort for its last steps.

## insSortAscNoDup()

template<class T>

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

## kthLargest()

template<class T>

T casacore::GenSort< T >::kthLargest | ( | T * | data,
|  | uInt | nr,
|  | uInt | k )

static

Find the k-th largest value.

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

## merge()

template<class T>

T * casacore::GenSort< T >::merge | ( | T * | data,
|  | T * | tmp,
|  | uInt | nrrec,
|  | uInt * | index,
|  | uInt | nparts )

static private

Thedata buffer is divided in nparts parts.

In each part the values are in ascending order. The index tells the nr of elements in each part. Recursively each two subsequent parts are merged until only part is left (giving the sorted array). Alternately data and tmp are used for the merge result. The pointer containing the final result is returned.
If possible, merging the parts is done in parallel (using OpenMP).

## parSort()

template<class T>

uInt casacore::GenSort< T >::parSort | ( | T * | ,
|  | uInt | nr,
|  | Sort::Order | = Sort::Ascending,
|  | int | options = 0,
|  | int | nthread = 0 )

static

Sort C-array using parallel merge sort (using OpenMP).

By default OpenMP determines the number of threads that can be used.

References casacore::Sort::Ascending.

## quickSort()

template<class T>

uInt casacore::GenSort< T >::quickSort | ( | T * | ,
|  | uInt | nr,
|  | Sort::Order | = Sort::Ascending,
|  | int | options = 0 )

static

Sort C-array using quicksort.

References casacore::Sort::Ascending.

## quickSortAsc()

template<class T>

void casacore::GenSort< T >::quickSortAsc | ( | T * | ,
|  | Int | ,
|  | Bool | multiThread = False,
|  | Int | rec_lim = 128 )

static private

Quicksort in ascending order.

References casacore::False.

## reverse()

template<class T>

void casacore::GenSort< T >::reverse | ( | T * | data,
|  | const T * | res,
|  | uInt | nrrec )

static

Reverse the elements in res and put them into data.

Care is taken if both pointers reference the same data.

## sort() [1/3]

template<class T>

uInt casacore::GenSort< T >::sort | ( | Array< T > & | ,
|  | Sort::Order | = Sort::Ascending,
|  | int | options = 0 )

static

References casacore::Sort::Ascending.

## sort() [2/3]

template<class T>

uInt casacore::GenSort< T >::sort | ( | Block< T > & | ,
|  | uInt | nr,
|  | Sort::Order | = Sort::Ascending,
|  | int | options = 0 )

static

References casacore::Sort::Ascending.

## sort() [3/3]

template<class T>

uInt casacore::GenSort< T >::sort | ( | T * | ,
|  | uInt | nr,
|  | Sort::Order | = Sort::Ascending,
|  | int | options = 0 )

static

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

The sort is done in place and is always stable (thus equal keys keep their original order). It returns the number of values, which can be different if a NoDuplicates sort is done.
Insertion sort is used for short arrays (<50 elements). Otherwise, a merge sort is used which will be parallelized if casacore is built with OpenMP support.

References casacore::Sort::Ascending.

Referenced by casacore::genSort(), casacore::genSort(), casacore::genSort(), and casacore::genSort().

## swap()

template<class T>

void casacore::GenSort< T >::swap | ( | T & | l,
|  | T & | r )

inline static

Swap 2 elements in array.

Implement inline member functions.

Definition at line 387 of file GenSort.h.

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

- casa/Utilities/GenSort.h