sort.h

Go to the documentation of this file.
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

Generated on 21 Nov 2012 for ergo by  doxygen 1.6.1