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