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
37 namespace 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
mat::quicksort
void quicksort(const Treal *value, int *index, int low, int high)
Definition: sort.h:42
mat
Definition: allocate.cc:39