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