ergo
|
00001 /* Ergo, version 3.2, a program for linear scaling electronic structure 00002 * calculations. 00003 * Copyright (C) 2012 Elias Rudberg, Emanuel H. Rubensson, and Pawel Salek. 00004 * 00005 * This program is free software: you can redistribute it and/or modify 00006 * it under the terms of the GNU General Public License as published by 00007 * the Free Software Foundation, either version 3 of the License, or 00008 * (at your option) any later version. 00009 * 00010 * This program is distributed in the hope that it will be useful, 00011 * but WITHOUT ANY WARRANTY; without even the implied warranty of 00012 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 00013 * GNU General Public License for more details. 00014 * 00015 * You should have received a copy of the GNU General Public License 00016 * along with this program. If not, see <http://www.gnu.org/licenses/>. 00017 * 00018 * Primary academic reference: 00019 * KohnâSham Density Functional Theory Electronic Structure Calculations 00020 * with Linearly Scaling Computational Time and Memory Usage, 00021 * Elias Rudberg, Emanuel H. Rubensson, and Pawel Salek, 00022 * J. Chem. Theory Comput. 7, 340 (2011), 00023 * <http://dx.doi.org/10.1021/ct100611z> 00024 * 00025 * For further information about Ergo, see <http://www.ergoscf.org>. 00026 */ 00027 00028 #ifndef MAT_SORT 00029 #define MAT_SORT 00030 namespace mat { 00031 00032 #if 1 00033 00034 template<class Treal> 00035 void quicksort(const Treal* value, int* index, int low, int high) 00036 throw(std::exception){ 00037 if(high >= low) 00038 { 00039 int i = low; 00040 int j = high; 00041 int tmp; 00042 Treal pivot = value[index[(low + high) / 2]]; /* Introduce the pivot */ 00043 do { /* Permute elements so that all */ 00044 while (value[index[i]] < pivot) i++; /* elements end up in one of */ 00045 while (value[index[j]] > pivot) j--; /* two groups, one where the */ 00046 if (i <= j) { /* elements have a value in value */ 00047 tmp = index[i]; /* smaller than the pivot and */ 00048 index[i] = index[j]; /* one group with a value larger*/ 00049 index[j] = tmp; /* than the pivot */ 00050 i++; 00051 j--; 00052 } 00053 } while (i <= j); 00054 if(low < j) quicksort(value, index, low, j); /* Sort the two groups */ 00055 if(i < high) quicksort(value, index, i, high); 00056 } 00057 } 00058 00059 #else 00060 00061 00062 template<typename Treal, typename Tfun> 00063 void quicksort(Tfun const & fun, int* index, int low, int high) 00064 throw(std::exception){ 00065 int i = low; 00066 int j = high; 00067 int tmp; 00068 Treal pivot = fun.value(index[(low + high) / 2]); /* Introduce pivot */ 00069 do { /* Permute elements so that all */ 00070 while (fun.value(index[i]) < pivot) i++;/* elements end up in one of*/ 00071 while (fun.value(index[j]) > pivot) j--;/* two groups, one where the*/ 00072 if (i <= j) { /* elements have a value in value */ 00073 tmp = index[i]; /* smaller than the pivot and */ 00074 index[i] = index[j]; /* one group with a value larger*/ 00075 index[j] = tmp; /* than the pivot */ 00076 i++; 00077 j--; 00078 } 00079 } while (i <= j); 00080 /* Sort the two groups */ 00081 if(low < j) quicksort<Treal>(fun, index, low, j); 00082 if(i < high) quicksort<Treal>(fun, index, i, high); 00083 } 00084 00085 template<class Treal> 00086 void quicksort(const Treal* value, int* index, int low, int high) { 00087 int i = low; 00088 int j = high; 00089 int tmp; 00090 Treal pivot = value[index[(low + high) / 2]]; /* Introduce the pivot */ 00091 do { /* Permute elements so that all */ 00092 while (value[index[i]] < pivot) i++; /* elements end up in one of */ 00093 while (value[index[j]] > pivot) j--; /* two groups, one where the */ 00094 if (i <= j) { /* elements have a value in value */ 00095 tmp = index[i]; /* smaller than the pivot and */ 00096 index[i] = index[j]; /* one group with a value larger*/ 00097 index[j] = tmp; /* than the pivot */ 00098 i++; 00099 j--; 00100 } 00101 } while (i <= j); 00102 if(low < j) quicksort(value, index, low, j); /* Sort the two groups */ 00103 if(i < high) quicksort(value, index, i, high); 00104 } 00105 00106 #endif 00107 00108 } /* end namespace mat */ 00109 00110 #endif