ergo
sort.h
Go to the documentation of this file.
1/* Ergo, version 3.8, a program for linear scaling electronic structure
2 * calculations.
3 * Copyright (C) 2019 Elias Rudberg, Emanuel H. Rubensson, Pawel Salek,
4 * and Anastasia Kruchinina.
5 *
6 * This program is free software: you can redistribute it and/or modify
7 * it under the terms of the GNU General Public License as published by
8 * the Free Software Foundation, either version 3 of the License, or
9 * (at your option) any later version.
10 *
11 * This program is distributed in the hope that it will be useful,
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 * GNU General Public License for more details.
15 *
16 * You should have received a copy of the GNU General Public License
17 * along with this program. If not, see <http://www.gnu.org/licenses/>.
18 *
19 * Primary academic reference:
20 * Ergo: An open-source program for linear-scaling electronic structure
21 * calculations,
22 * Elias Rudberg, Emanuel H. Rubensson, Pawel Salek, and Anastasia
23 * Kruchinina,
24 * SoftwareX 7, 107 (2018),
25 * <http://dx.doi.org/10.1016/j.softx.2018.03.005>
26 *
27 * For further information about Ergo, see <http://www.ergoscf.org>.
28 */
29
35#ifndef MAT_SORT
36#define MAT_SORT
37namespace mat {
38
39#if 1
40
41 template<class Treal>
42 void quicksort(const Treal* value, int* index, int low, int high)
43 {
44 if(high >= low)
45 {
46 int i = low;
47 int j = high;
48 int tmp;
49 Treal pivot = value[index[(low + high) / 2]]; /* Introduce the pivot */
50 do { /* Permute elements so that all */
51 while (value[index[i]] < pivot) i++; /* elements end up in one of */
52 while (value[index[j]] > pivot) j--; /* two groups, one where the */
53 if (i <= j) { /* elements have a value in value */
54 tmp = index[i]; /* smaller than the pivot and */
55 index[i] = index[j]; /* one group with a value larger*/
56 index[j] = tmp; /* than the pivot */
57 i++;
58 j--;
59 }
60 } while (i <= j);
61 if(low < j) quicksort(value, index, low, j); /* Sort the two groups */
62 if(i < high) quicksort(value, index, i, high);
63 }
64 }
65
66#else
67
68
69 template<typename Treal, typename Tfun>
70 void quicksort(Tfun const & fun, int* index, int low, int high)
71 throw(std::exception){
72 int i = low;
73 int j = high;
74 int tmp;
75 Treal pivot = fun.value(index[(low + high) / 2]); /* Introduce pivot */
76 do { /* Permute elements so that all */
77 while (fun.value(index[i]) < pivot) i++;/* elements end up in one of*/
78 while (fun.value(index[j]) > pivot) j--;/* two groups, one where the*/
79 if (i <= j) { /* elements have a value in value */
80 tmp = index[i]; /* smaller than the pivot and */
81 index[i] = index[j]; /* one group with a value larger*/
82 index[j] = tmp; /* than the pivot */
83 i++;
84 j--;
85 }
86 } while (i <= j);
87 /* Sort the two groups */
88 if(low < j) quicksort<Treal>(fun, index, low, j);
89 if(i < high) quicksort<Treal>(fun, index, i, high);
90 }
91
92 template<class Treal>
93 void quicksort(const Treal* value, int* index, int low, int high) {
94 int i = low;
95 int j = high;
96 int tmp;
97 Treal pivot = value[index[(low + high) / 2]]; /* Introduce the pivot */
98 do { /* Permute elements so that all */
99 while (value[index[i]] < pivot) i++; /* elements end up in one of */
100 while (value[index[j]] > pivot) j--; /* two groups, one where the */
101 if (i <= j) { /* elements have a value in value */
102 tmp = index[i]; /* smaller than the pivot and */
103 index[i] = index[j]; /* one group with a value larger*/
104 index[j] = tmp; /* than the pivot */
105 i++;
106 j--;
107 }
108 } while (i <= j);
109 if(low < j) quicksort(value, index, low, j); /* Sort the two groups */
110 if(i < high) quicksort(value, index, i, high);
111 }
112
113#endif
114
115} /* end namespace mat */
116
117#endif
Definition: allocate.cc:39
void quicksort(const Treal *value, int *index, int low, int high)
Definition: sort.h:42