|
|
template <class T> void sort(T* b,T* e); template <class T> void sort_r(int (*rel)(const T*,const T*),T* b,T* e); template <class T> void sort_rs(int (*rel)(const T*,const T*),T* b,T* e); template <class T> void sort_s(T* b,T* e);
(1) For the non-relational versions, T::operator< defines a total ordering relation on T.
(2) For the relational version, rel defines a total ordering relation on T.
(S) T has operator=.
These functions sort an array in place.
template <class T> void sort(T* b,T* e);
Uses T::operator< to define the ordering relation used by the sorting algorithm sort is not stable; that is, it does not preserve the relative order of equal elements.
template <class T> void sort_r(int (*rel)(const T*,const T*),T* b,T* e);
Uses rel to define the ordering relation used by the sorting algorithm.
template <class T> void sort_rs(int (*rel)(const T*,const T*),T* b,T* e);
Like sort_r except that it uses a stable algorithm. That is, the relative order of equal elements is preserved.
template <class T> void sort_s(T* b,T* e);
Like sort except that it uses a stable algorithm. That is, the relative order of equal elements is preserved.
If N is the size of the array, then complexity is O(NlgN) on average. Complexity is O(N*N) in the worst case, which is highly improbable.
The non-stable versions use drand48(3C) to obtain pseudo-random numbers.
Because a Block (see Block(3C++)) can always be used wherever an array is called for, Array Algorithms can also be used with Blocks. In fact, these two components were actually designed to be used together.
Array_alg(3C++) drand48(3C) ins_sort(3C++) merge_sort(3C++) Block(3C++)