167 void QuickSort(
int low,
int high, T data[]);
170 void HeapSort(
int low,
int high, T data[]);
173 void InsertSort(
int low,
int high, T data[]);
190 s.sort(0, data.
size() - 1, data);
206 return s.sort_index(0, data.
size() - 1, data);
223 "low or high out of bounds");
225 switch (sort_method) {
239 it_error(
"Sort<T>::sort(): Unknown sorting method");
255 "low or high out of bounds");
258 for (
int i = 0;
i < N; ++
i) {
262 switch (sort_method) {
277 it_error(
"Sort<T>::sort_index(): Unknown sorting method");
289 "Sort::sort(): low or high out of bounds");
300 "Sort::sort(): low or high out of bounds");
303 for (
int i = 0;
i < N; ++
i) {
331 T test =
data[phigh];
332 while (plow < phigh) {
345 IntroSort(low, plow - 1, max_depth,
data);
346 IntroSort(plow + 1, high, max_depth,
data);
351 InsertSort(low, high,
data);
357void Sort<T>::IntroSort_Index(
int low,
int high,
int max_depth,
358 int indexlist[],
const T data[])
360 if (high - low > 16) {
362 if (max_depth == 0) {
363 HeapSort_Index(low, high, indexlist,
data);
368 int aindex = indexlist[low];
372 int testindex = indexlist[phigh];
373 T test =
data[testindex];
374 while (plow < phigh) {
376 indexlist[plow] = testindex;
378 testindex = indexlist[plow];
379 test =
data[testindex];
382 indexlist[phigh] = testindex;
384 testindex = indexlist[phigh];
385 test =
data[testindex];
388 indexlist[plow] = aindex;
389 IntroSort_Index(low, plow - 1, max_depth, indexlist,
data);
390 IntroSort_Index(plow + 1, high, max_depth, indexlist,
data);
394 InsertSort_Index(low, high, indexlist,
data);
400void Sort<T>::QuickSort(
int low,
int high, T data[])
406 T test =
data[phigh];
407 while (plow < phigh) {
420 QuickSort(low, plow - 1,
data);
421 QuickSort(plow + 1, high,
data);
426void Sort<T>::QuickSort_Index(
int low,
int high,
int indexlist[],
430 int aindex = indexlist[low];
434 int testindex = indexlist[phigh];
435 T test =
data[testindex];
436 while (plow < phigh) {
438 indexlist[plow] = testindex;
440 testindex = indexlist[plow];
441 test =
data[testindex];
444 indexlist[phigh] = testindex;
446 testindex = indexlist[phigh];
447 test =
data[testindex];
450 indexlist[plow] = aindex;
451 QuickSort_Index(low, plow - 1, indexlist,
data);
452 QuickSort_Index(plow + 1, high, indexlist,
data);
457void Sort<T>::HeapSort(
int low,
int high, T data[])
459 int size = (high + 1) - low;
464 temp =
data[--i + low];
473 int child = i * 2 + 1;
475 while (child <
size) {
476 if (child + 1 <
size &&
data[child + 1 + low] >
data[child + low])
478 if (
data[child + low] > temp) {
479 data[parent + low] =
data[child + low];
481 child = parent * 2 + 1;
486 data[parent + low] = temp;
491void Sort<T>::HeapSort_Index(
int low,
int high,
int indexlist[],
494 int size = (high + 1) - low;
502 tempValue =
data[indexlist[i + low]];
503 tempIndex = indexlist[i + low];
508 tempValue =
data[indexlist[
size + low]];
509 tempIndex = indexlist[
size + low];
510 indexlist[
size+low] = indexlist[low];
514 int child = i * 2 + 1;
516 while (child <
size) {
517 if ((child + 1 <
size)
518 &&
data[indexlist[child + 1 + low]] >
data[indexlist[child + low]])
520 if (
data[indexlist[child + low]] > tempValue) {
521 indexlist[parent + low] = indexlist[child + low];
523 child = parent * 2 + 1;
528 indexlist[parent + low] = tempIndex;
533void Sort<T>::InsertSort(
int low,
int high, T data[])
535 for (
int i = low + 1; i <= high; i++) {
538 for (j = i - 1; j >= low &&
data[j] > value; j--) {
546void Sort<T>::InsertSort_Index(
int low,
int high,
int indexlist[],
549 for (
int i = low + 1; i <= high; i++) {
550 T value =
data[indexlist[i]];
551 int tempIndex = indexlist[i];
553 for (j = i - 1; j >= low &&
data[indexlist[j]] > value; j--) {
554 indexlist[j + 1] = indexlist[j];
556 indexlist[j + 1] = tempIndex;
int size() const
Returns the number of data elements in the array object.
T * data
A pointer to the data area.
Class for sorting of vectors.
void sort(int low, int high, Vec< T > &data)
Sorting function of a subset of a vector data.
void set_method(SORTING_METHOD method)
Set sorting method.
SORTING_METHOD get_method() const
Get current sorting method.
void intro_sort(int low, int high, int max_depth, Vec< T > &data)
Introsort function of a subset of a vector data.
ivec sort_index(int low, int high, const Vec< T > &data)
Sorting function that returns a sorted index vector.
ivec intro_sort_index(int low, int high, int max_depth, const Vec< T > &data)
Introsort function, which returns a sorted index vector.
Sort(SORTING_METHOD method=INTROSORT)
Constructor that sets Intro Sort method by default.
ivec sort_index(const Vec< T > &data, SORTING_METHOD method=INTROSORT)
Return an index vector corresponding to a sorted vector data in increasing order.
void sort(Vec< T > &data, SORTING_METHOD method=INTROSORT)
Sort the data vector in increasing order.
Definitions of converters between different vector and matrix types.
#define it_error(s)
Abort unconditionally.
#define it_assert(t, s)
Abort if t is not true.
int levels2bits(int n)
Calculate the number of bits needed to represent n different values (levels).
Logarithmic and exponenential functions - header file.
SORTING_METHOD
Sorting algorithms that can be used in a Sort class.
Templated Vector Class Definitions.