Документ взят из кэша поисковой машины. Адрес
оригинального документа
: http://www.atnf.csiro.au/computing/software/casacore/casacore-1.2.0/doc/html/classcasa_1_1GenSort.html
Дата изменения: Unknown Дата индексирования: Mon Feb 14 20:41:37 2011 Кодировка: Поисковые слова: п п п п п п п п п п п п п |
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. |
General in-place sort functions.
Internal
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:
Array
s of values -- the array can have any shape and the increment can be >1; Block
s 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) Sort::HeapSort
Sort::InsSort
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.
operator=
to assign when swapping elements operator<
, operator>
and operator==
to compare elements Definition at line 108 of file GenSort.h.
static void casa::GenSort< T >::heapAscSiftDown | ( | Int | , | |
Int | , | |||
T * | ||||
) | [static, private] |
Helper function for ascending heapsort.
static void casa::GenSort< T >::heapDescSiftDown | ( | Int | , | |
Int | , | |||
T * | ||||
) | [static, private] |
Helper function for descending heapsort.
static uInt casa::GenSort< T >::heapSort | ( | T * | , | |
uInt | nr, | |||
Sort::Order | , | |||
int | options | |||
) | [static, private] |
Sort C-array using heapsort.
static void casa::GenSort< T >::heapSortAsc | ( | T * | , | |
Int | ||||
) | [static, private] |
Heapsort in ascending order.
static void casa::GenSort< T >::heapSortDesc | ( | T * | , | |
Int | ||||
) | [static, private] |
Heapsort in descending order.
static uInt casa::GenSort< T >::insSort | ( | T * | , | |
uInt | nr, | |||
Sort::Order | , | |||
int | options | |||
) | [static, private] |
Sort C-array using insertion sort.
static uInt casa::GenSort< T >::insSortAsc | ( | T * | , | |
Int | , | |||
int | option | |||
) | [static, private] |
Insertion sort in ascending order.
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.
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.
static uInt casa::GenSort< T >::insSortDesc | ( | T * | , | |
Int | , | |||
int | option | |||
) | [static, private] |
Insertion sort in descending order.
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.
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.
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.\.
static uInt casa::GenSort< T >::quickSort | ( | T * | , | |
uInt | nr, | |||
Sort::Order | , | |||
int | options | |||
) | [static, private] |
Sort C-array using quicksort.
static void casa::GenSort< T >::quickSortAsc | ( | T * | , | |
Int | ||||
) | [static, private] |
Quicksort in ascending order.
static void casa::GenSort< T >::quickSortDesc | ( | T * | , | |
Int | ||||
) | [static, private] |
Quicksort in descending order.
static uInt casa::GenSort< T >::sort | ( | Block< T > & | , | |
uInt | nr, | |||
Sort::Order | = Sort::Ascending , |
|||
int | options = Sort::QuickSort | |||
) | [static] |
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().
static uInt casa::GenSort< T >::sort | ( | Array< T > & | , | |
Sort::Order | = Sort::Ascending , |
|||
int | options = Sort::QuickSort | |||
) | [static] |
void casa::GenSort< T >::swap | ( | T & | l, | |
T & | r | |||
) | [inline, static, private] |