sort.h
Go to the documentation of this file.00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
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]];
00043 do {
00044 while (value[index[i]] < pivot) i++;
00045 while (value[index[j]] > pivot) j--;
00046 if (i <= j) {
00047 tmp = index[i];
00048 index[i] = index[j];
00049 index[j] = tmp;
00050 i++;
00051 j--;
00052 }
00053 } while (i <= j);
00054 if(low < j) quicksort(value, index, low, j);
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]);
00069 do {
00070 while (fun.value(index[i]) < pivot) i++;
00071 while (fun.value(index[j]) > pivot) j--;
00072 if (i <= j) {
00073 tmp = index[i];
00074 index[i] = index[j];
00075 index[j] = tmp;
00076 i++;
00077 j--;
00078 }
00079 } while (i <= j);
00080
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]];
00091 do {
00092 while (value[index[i]] < pivot) i++;
00093 while (value[index[j]] > pivot) j--;
00094 if (i <= j) {
00095 tmp = index[i];
00096 index[i] = index[j];
00097 index[j] = tmp;
00098 i++;
00099 j--;
00100 }
00101 } while (i <= j);
00102 if(low < j) quicksort(value, index, low, j);
00103 if(i < high) quicksort(value, index, i, high);
00104 }
00105
00106 #endif
00107
00108 }
00109
00110 #endif