メインページ | アルファベット順一覧 | 構成 | ファイル一覧 | 構成メンバ | ファイルメンバ | 関連ページ

dkcSort.c

説明を見る。
00001 
00007 #define DKUTIL_C_SORT_C
00008 #include "dkcSort.h"
00009 
00010 
00011 
00012 
00013 
00014 //void qsort( void *base, size_t num, size_t width, int (__cdecl *compare)(const void *elem1, const void *elem2) );
00015 
00016 void WINAPI dkcShellSort( void *base,size_t num,size_t width,DKC_SORT_COMPARE_TYPE compare){
00017     //(int n, keytype a[])  /* a[0..n-1] を昇順に */
00018 
00019     int h, i, j;
00020     int n = (int)num;
00021     BYTE *x = (BYTE *)malloc(width);
00022     BYTE *a = (BYTE *)base;
00023 
00024     //BYTE *end = a + ((num - 1) * width);
00025 
00026     h = 13;
00027     while (h < n){
00028         h = 3 * h + 1;
00029     }
00030     //h /= 9;
00031     h = ( h - 1 ) / 3;
00032     while (h > 0) {
00033         for (i = h; i < n; i++) {
00034             //x = a[i];
00035             //memmove(x,&a[i * width],width);
00036             dkcSwap(x,&a[i * width],width);
00037             for (j = i - h;
00038                 j >= 0 ; /*a[j * width] > x*/
00039                 j -= h)
00040             {
00041                 if(compare(&a[j * width],x) > 0)
00042                 {
00043                     //a[(j + h) * width] = a[j * width];
00044                     dkcSwap(&a[(j + h) * width] , &a[j * width],width);
00045                 }else{
00046                     break;
00047                 }
00048             }
00049             //a[(j + h) * width] = x;
00050             //memmove(&a[(j + h) * width], x ,width);
00051             dkcSwap(&a[(j + h) * width],x ,width);
00052         }
00053         //h /= 3;
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/* *(b+j-1) > *(b+j) */)
00067             {
00068          dkcSwap(&b[(j-1) * width],&b[j*width],width);
00069       }
00070     }
00071   }
00072 
00073 
00074 
00075 }
00076 
00077 /*
00078 2004/07/07 http://www2s.biglobe.ne.jp/~nuts/labo/daal/daal06.html より引用
00079 n は 要素数より小さい任意の数から始まって、
00080 i = ∞ で ni = 1 となる。実際には n1 = 要素数 - 1、ni+1 = ni / 1.3 あたりが良いらしい。
00081 実装では n = ( n * 10 + 3 ) / 13 として、小数点演算を避けると共に、 +3 して n = 0 となるのを完全に防ぐ方法が用いられる。 
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       //if ( b[j] < b[i] ) {
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     //static int count[Max_ - Min_ + 1];
00132     //int *count = (int *)malloc(sizeof(int) * (Max_ - Min_ + 1));
00133     //int *count = (int *)dkcAllocate(sizeof(int) * (Max_ - Min_ + 1));
00134     int *count = (int *)dkcAllocate(sizeof(int) * (abs(Max_) + abs(Min_) + 1 ));
00135     if(NULL==count){
00136         return edk_OutOfMemory;
00137     }
00138     //for (i = 0; i <= Max_ - Min_; i++) count[i] = 0;
00139     //memset(count,0,sizeof(
00140     //for (i = 0; i <= Max_ - Min_; i++) count[i] = 0;
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]; //debugged
00151         //x = a[i] - Min_;  b[--count[x]] = x;//origin
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         //count[i] += count[i - 1];
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]; //debugged
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         //count[i] += count[i - 1];
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]; //debugged
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         //count[i] += count[i - 1];
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]; //debugged
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         //count[i] += (char)count[i - 1];
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]; //debugged
00254     }
00255     dkcFree((void **)&count);
00256     return edk_SUCCEEDED;
00257 
00258 
00259 }
00260 #endif

dkutil_cに対してSat Sep 10 09:23:57 2005に生成されました。  doxygen 1.4.4