00001
00007 #define DKUTIL_C_SORT_C
00008 #include "dkcSort.h"
00009
00010
00011
00012
00013
00014
00015
00016 void WINAPI dkcShellSort( void *base,size_t num,size_t width,DKC_SORT_COMPARE_TYPE compare){
00017
00018
00019 int h, i, j;
00020 int n = (int)num;
00021 BYTE *x = (BYTE *)malloc(width);
00022 BYTE *a = (BYTE *)base;
00023
00024
00025
00026 h = 13;
00027 while (h < n){
00028 h = 3 * h + 1;
00029 }
00030
00031 h = ( h - 1 ) / 3;
00032 while (h > 0) {
00033 for (i = h; i < n; i++) {
00034
00035
00036 dkcSwap(x,&a[i * width],width);
00037 for (j = i - h;
00038 j >= 0 ;
00039 j -= h)
00040 {
00041 if(compare(&a[j * width],x) > 0)
00042 {
00043
00044 dkcSwap(&a[(j + h) * width] , &a[j * width],width);
00045 }else{
00046 break;
00047 }
00048 }
00049
00050
00051 dkcSwap(&a[(j + h) * width],x ,width);
00052 }
00053
00054 h = ( h - 1 ) / 3;
00055 }
00056 free(x);
00057 }
00058
00059 void WINAPI dkcBubbleSort( void *base,size_t num,size_t width,DKC_SORT_COMPARE_TYPE compare)
00060 {
00061 BYTE *b = (BYTE *)base;
00062 size_t i, j;
00063
00064 for(i=0; i<num-1; i++){
00065 for(j=num-1; j>i; j--){
00066 if(compare(&b[(j-1) * width],&b[j*width]) > 0)
00067 {
00068 dkcSwap(&b[(j-1) * width],&b[j*width],width);
00069 }
00070 }
00071 }
00072
00073
00074
00075 }
00076
00077
00078
00079
00080
00081
00082
00083 void WINAPI dkcCombSort( void *base,size_t num,size_t width,DKC_SORT_COMPARE_TYPE compare){
00084
00085 BYTE *b = (BYTE *)base;
00086 int gap = num;
00087 size_t first2 = num;
00088 BOOL swapped = FALSE;
00089 int newgap;
00090 size_t i,j;
00091 if ( gap < 1 ) {
00092 dkcBubbleSort(base,num,width,compare);
00093 return;
00094 }
00095
00096 do {
00097 newgap = (gap*10+3)/13;
00098 if ( newgap < 1 ) newgap = 1;
00099 first2 += newgap - gap;
00100 gap = newgap;
00101 swapped = FALSE;
00102 for (i = 0, j = first2;
00103 j != num;
00104 ++i, ++j) {
00105
00106 if(compare(&b[i*width],&b[j*width]) > 0)
00107 {
00108 dkcSwap(&b[j*width],&b[i*width],width);
00109 swapped = TRUE;
00110 }
00111 }
00112 } while ( (gap > 1) || swapped );
00113 }
00114
00115
00116
00117 void WINAPI dkcQuickSort( void *base,size_t num,size_t width,DKC_SORT_COMPARE_TYPE compare)
00118 {
00119 qsort(base,num,width,compare);
00120 }
00121
00122
00123
00124
00125
00126 int WINAPI dkcDistCountSortInt(size_t num, const int *a, int *b,int Min_,int Max_)
00127 {
00128
00129 int i, x;
00130 size_t ii;
00131
00132
00133
00134 int *count = (int *)dkcAllocate(sizeof(int) * (abs(Max_) + abs(Min_) + 1 ));
00135 if(NULL==count){
00136 return edk_OutOfMemory;
00137 }
00138
00139
00140
00141
00142 for (ii = 0; ii < num; ii++){
00143 count[a[ii] - Min_]++;
00144 }
00145
00146 for (i = 1; i <= Max_ - Min_; i++){
00147 count[i] += count[i - 1];
00148 }
00149 for (i = num - 1; i >= 0; i--) {
00150 x = a[i] - Min_; b[--count[x]] = a[i];
00151
00152 }
00153 dkcFree((void **)&count);
00154 return edk_SUCCEEDED;
00155
00156 }
00157
00158 int WINAPI dkcDistCountSortShort(size_t num, const short *a, short *b,short Min_,short Max_)
00159 {
00160 int i, x;
00161 size_t ii;
00162 short *count = (short*)dkcAllocate(sizeof(short) * (abs(Max_) + abs(Min_) + 1 ));
00163
00164 if(NULL==count){
00165 return edk_OutOfMemory;
00166 }
00167
00168
00169 for (ii = 0; ii < num; ii++){
00170 count[a[ii] - Min_]++;
00171 }
00172
00173 for (i = 1; i <= Max_ - Min_; i++){
00174
00175 count[i] = (short)(count[i] + count[i - 1]);
00176 }
00177 for (i = num - 1; i >= 0; i--) {
00178 x = a[i] - Min_; b[--count[x]] = a[i];
00179 }
00180 dkcFree((void **)&count);
00181 return edk_SUCCEEDED;
00182 }
00183
00184 int WINAPI dkcDistCountSortChar(size_t num, const char *a, char *b,char Min_,char Max_)
00185 {
00186 int i, x;
00187 size_t ii;
00188 char *count = (char*)dkcAllocate(sizeof(char) * (abs(Max_) + abs(Min_) + 1 ));
00189 if(NULL==count){
00190 return edk_OutOfMemory;
00191 }
00192
00193
00194 for (ii = 0; ii < num; ii++){
00195 count[a[ii] - Min_]++;
00196 }
00197
00198 for (i = 1; i <= Max_ - Min_; i++){
00199
00200 count[i] = (char)(count[i] + count[i - 1]);
00201 }
00202 for (i = num - 1; i >= 0; i--) {
00203 x = a[i] - Min_; b[--count[x]] = a[i];
00204 }
00205 dkcFree((void **)&count);
00206 return edk_SUCCEEDED;
00207
00208
00209 }
00210 #if 0
00211 int WINAPI dkcDistCountSortShort(size_t num, const short *a, short *b,short Min_,short Max_)
00212 {
00213 int i, x;
00214 size_t ii;
00215
00216 short *count = (short *)dkcAllocate(sizeof(short) * (Max_));
00217 if(NULL==count){
00218 return edk_OutOfMemory;
00219 }
00220 for (ii = 0; ii < num; ii++){
00221 count[a[ii] - Min_]++;
00222 }
00223
00224 for (i = 1; i <= Max_ - Min_; i++){
00225
00226 count[i] = (short)(count[i] + count[i - 1]);
00227 }
00228 for (i = num - 1; i >= 0; i--) {
00229 x = a[i] - Min_; b[--count[x]] = a[i];
00230 }
00231 dkcFree((void **)&count);
00232 return edk_SUCCEEDED;
00233 }
00234
00235 int WINAPI dkcDistCountSortChar(size_t num, const char *a, char *b,char Min_,char Max_)
00236 {
00237 int i, x;
00238 size_t ii;
00239
00240 char *count = (char *)dkcAllocate(sizeof(char) * (Max_));
00241 if(NULL==count){
00242 return edk_OutOfMemory;
00243 }
00244 for (ii = 0; ii < num; ii++){
00245 count[a[ii] - Min_]++;
00246 }
00247
00248 for (i = 1; i <= Max_ - Min_; i++){
00249
00250 count[i] = (char)(count[i] + count[i - 1]);
00251 }
00252 for (i = num - 1; i >= 0; i--) {
00253 x = a[i] - Min_; b[--count[x]] = a[i];
00254 }
00255 dkcFree((void **)&count);
00256 return edk_SUCCEEDED;
00257
00258
00259 }
00260 #endif