/usr/lib/grass70/include/grass/iostream/quicksort.h is in grass-dev 7.0.3-1build1.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 | /****************************************************************************
*
* MODULE: iostream
*
* COPYRIGHT (C) 2007 Laura Toma
*
*
* Iostream is a library that implements streams, external memory
* sorting on streams, and an external memory priority queue on
* streams. These are the fundamental components used in external
* memory algorithms.
* Credits: The library was developed by Laura Toma. The kernel of
* class STREAM is based on the similar class existent in the GPL TPIE
* project developed at Duke University. The sorting and priority
* queue have been developed by Laura Toma based on communications
* with Rajiv Wickremesinghe. The library was developed as part of
* porting Terraflow to GRASS in 2001. PEARL upgrades in 2003 by
* Rajiv Wickremesinghe as part of the Terracost project.
*
* This program is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation; either version 2 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
* General Public License for more details. *
* **************************************************************************/
#ifndef _QUICKSORT_H
#define _QUICKSORT_H
#include <stdlib.h> //for random()
// The class represented by CMPR, must have a member function called
// "compare" which is used for sorting
/* ---------------------------------------------------------------------- */
// On return from partition(), everything at or below pivot will be
// less that or equal to everything above it. Furthermore, it will
// not be 0 since this will leave us to recurse on the whole array
// again.
template<class T, class CMPR>
void partition(T *data, size_t n, size_t &pivot, CMPR &cmp) {
T *ptpart, tpart;
T *p, *q;
T t0;
// Try to get a good partition value and avoid being bitten by already
// sorted input.
//ptpart = data + (random() % n);
#ifdef __MINGW32__
ptpart = data + (rand() % n);
#else
ptpart = data + (random() % n);
#endif
tpart = *ptpart;
*ptpart = data[0];
data[0] = tpart;
// Walk through the array and partition it.
for (p = data - 1, q = data + n; ; ) {
do {
q--;
} while (cmp.compare(*q, tpart) > 0);
do {
p++;
} while (cmp.compare(*p, tpart) < 0);
if (p < q) {
t0 = *p;
*p = *q;
*q = t0;
} else {
pivot = q - data;
break;
}
}
}
/* ---------------------------------------------------------------------- */
template<class T, class CMPR>
void insertionsort(T *data, size_t n, CMPR &cmp) {
T *p, *q, test;
for (p = data + 1; p < data + n; p++) {
for (q = p - 1, test = *p; (cmp.compare(*q, test) > 0); q--) {
*(q+1) = *q;
if (q==data) {
q--; // to make assignment below correct
break;
}
}
*(q+1) = test;
}
}
/* ---------------------------------------------------------------------- */
template<class T, class CMPR>
void quicksort(T *data, size_t n, CMPR &cmp, size_t min_len = 20) {
size_t pivot;
if (n < min_len) {
insertionsort(data, n, cmp);
return;
}
//else
partition(data, n, pivot, cmp);
quicksort(data, pivot + 1, cmp, min_len);
quicksort(data + pivot + 1, n - pivot - 1, cmp, min_len);
}
#endif // _QUICKSORT_H
|