GRASS GIS 8 Programmer's Manual  8.5.0dev(2024)-ee9fa48798
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 #ifndef _QUICKSORT_H
37 #define _QUICKSORT_H
38 
39 #include <stdlib.h> //for random()
40 
41 // The class represented by CMPR, must have a member function called
42 // "compare" which is used for sorting
43 
44 /* ---------------------------------------------------------------------- */
45 // On return from partition(), everything at or below pivot will be
46 // less that or equal to everything above it. Furthermore, it will
47 // not be 0 since this will leave us to recurse on the whole array
48 // again.
49 template <class T, class CMPR>
50 void partition(T *data, size_t n, size_t &pivot, CMPR &cmp)
51 {
52  T *ptpart, tpart;
53  T *p, *q;
54  T t0;
55 
56  // Try to get a good partition value and avoid being bitten by already
57  // sorted input.
58  // ptpart = data + (random() % n);
59 #ifdef __MINGW32__
60  ptpart = data + (rand() % n);
61 #else
62  ptpart = data + (random() % n);
63 #endif
64 
65  tpart = *ptpart;
66  *ptpart = data[0];
67  data[0] = tpart;
68 
69  // Walk through the array and partition it.
70  for (p = data - 1, q = data + n;;) {
71 
72  do {
73  q--;
74  } while (cmp.compare(*q, tpart) > 0);
75  do {
76  p++;
77  } while (cmp.compare(*p, tpart) < 0);
78 
79  if (p < q) {
80  t0 = *p;
81  *p = *q;
82  *q = t0;
83  }
84  else {
85  pivot = q - data;
86  break;
87  }
88  }
89 }
90 
91 /* ---------------------------------------------------------------------- */
92 template <class T, class CMPR>
93 void insertionsort(T *data, size_t n, CMPR &cmp)
94 {
95  T *p, *q, test;
96 
97  for (p = data + 1; p < data + n; p++) {
98  for (q = p - 1, test = *p; (cmp.compare(*q, test) > 0); q--) {
99  *(q + 1) = *q;
100  if (q == data) {
101  q--; // to make assignment below correct
102  break;
103  }
104  }
105  *(q + 1) = test;
106  }
107 }
108 
109 /* ---------------------------------------------------------------------- */
110 template <class T, class CMPR>
111 void quicksort(T *data, size_t n, CMPR &cmp, size_t min_len = 20)
112 {
113 
114  size_t pivot;
115  if (n < min_len) {
116  insertionsort(data, n, cmp);
117  return;
118  }
119  // else
120  partition(data, n, pivot, cmp);
121  quicksort(data, pivot + 1, cmp, min_len);
122  quicksort(data + pivot + 1, n - pivot - 1, cmp, min_len);
123 }
124 
125 #endif // _QUICKSORT_H
void partition(T *data, size_t n, size_t &pivot, CMPR &cmp)
Definition: quicksort.h:50
void insertionsort(T *data, size_t n, CMPR &cmp)
Definition: quicksort.h:93
void quicksort(T *data, size_t n, CMPR &cmp, size_t min_len=20)
Definition: quicksort.h:111