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

# dkcSort.h

sort utility... qsort() like [詳細]

`#include "dkcOSIndependent.h"`
`#include "dkcBlockSort.h"`

dkcSort.hのインクルード依存関係図

このグラフは、どのファイルから直接、間接的にインクルードされているかを示しています。

ソースコードを見る。

## 型定義
typedef DKC_COMPARE_TYPE | DKC_SORT_COMPARE_TYPE
## 関数
DKC_EXTERN void WINAPI | dkcShellSort (void *base, size_t num, size_t width, DKC_SORT_COMPARE_TYPE compare)
DKC_EXTERN void WINAPI | dkcCombSort (void *base, size_t num, size_t width, DKC_SORT_COMPARE_TYPE compare)
DKC_EXTERN void WINAPI | dkcBubbleSort (void *base, size_t num, size_t width, DKC_SORT_COMPARE_TYPE compare)
DKC_EXTERN void WINAPI | dkcBitonicSort (void *base, size_t num, size_t width, DKC_SORT_COMPARE_TYPE compare)
DKC_EXTERN void WINAPI | dkcQuickSort (void *base, size_t num, size_t width, DKC_SORT_COMPARE_TYPE compare)
DKC_EXTERN void WINAPI | dkcMultiPartitionSort (void *base, size_t num, size_t width, DKC_SORT_COMPARE_TYPE compare)
DKC_EXTERN int WINAPI | dkcDistCountSortInt (size_t num, const int *src, int *dest, int Min_, int Max_)
DKC_EXTERN int WINAPI | dkcDistCountSortShort (size_t num, const short *src, short *dest, short Min_, short Max_)
DKC_EXTERN int WINAPI | dkcDistCountSortChar (size_t num, const char *src, char *dest, char Min_, char Max_)

## 説明

sort utility... qsort() like

作者:
  d金魚

から:
  2004/04/28

覚え書き:
  sort系のものたくさん。

dkcSort.h で定義されています。

## 型定義

typedef DKC_COMPARE_TYPE DKC_SORT_COMPARE_TYPE

| dkcSort.h の 16 行で定義されています。

## 関数

DKC_EXTERN void WINAPI dkcBitonicSort | ( | void * | base,
|  | size_t | num,
|  | size_t | width,
|  | DKC_SORT_COMPARE_TYPE | compare
| ) |

| いわいるバイトニックソートをする。 TODO: 実装できないかもしれない。

DKC_EXTERN void WINAPI dkcBubbleSort | ( | void * | base,
|  | size_t | num,
|  | size_t | width,
|  | DKC_SORT_COMPARE_TYPE | compare
| ) |

| いわゆるバブルソートをする。 dkcSort.c の 59 行で定義されています。 参照先 BYTE, と dkcSwap(). 参照元 dkcCombSort().
    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 }

DKC_EXTERN void WINAPI dkcCombSort | ( | void * | base,
|  | size_t | num,
|  | size_t | width,
|  | DKC_SORT_COMPARE_TYPE | compare
| ) |

| いわいるコムソートをする。 dkcSort.c の 83 行で定義されています。 参照先 BYTE, dkcBubbleSort(), dkcSwap(), FALSE, と TRUE.
    00083                                                                                           {
    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 }

DKC_EXTERN int WINAPI dkcDistCountSortChar | ( | size_t | num,
|  | const char * | src,
|  | char * | dest,
|  | char | Min_,
|  | char | Max_
| ) |

| 参照: dkcDistCountSortInt() dkcSort.c の 184 行で定義されています。 参照先 dkcAllocate(), dkcFree(), と NULL.
    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 }

DKC_EXTERN int WINAPI dkcDistCountSortInt | ( | size_t | num,
|  | const int * | src,
|  | int * | dest,
|  | int | Min_,
|  | int | Max_
| ) |

| Distribution count sort 分布数えソート。大量の記憶領域を使うがO(n)で極速！ しかし、仮想記憶上ではほぼ意味無しか！？ 覚え書き: dkcDistCountSortShort()やdkcDistCountSortChar()は遅いと思います。 Min_ と Max_ の差が大きいほど　メモリを使います。 sizeof(type) * (abs(Max_) + abs(Min_) + 1 )バイトほど使います。詳しくはソースを見てください。 <s>０〜USHRT_MAXまでの値しか使えません。ヽ(`Д´)ﾉｳﾜｧﾝ</s> 戻り値: edk_SUCCEEDEDで成功 dkcSort.c の 126 行で定義されています。 参照先 dkcAllocate(), dkcFree(), と NULL.
    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 }

DKC_EXTERN int WINAPI dkcDistCountSortShort | ( | size_t | num,
|  | const short * | src,
|  | short * | dest,
|  | short | Min_,
|  | short | Max_
| ) |

| 参照: dkcDistCountSortInt() dkcSort.c の 158 行で定義されています。 参照先 dkcAllocate(), dkcFree(), と NULL.
    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 }

DKC_EXTERN void WINAPI dkcMultiPartitionSort | ( | void * | base,
|  | size_t | num,
|  | size_t | width,
|  | DKC_SORT_COMPARE_TYPE | compare
| ) |

| いわいるマルチパーテーションソート（多重分割ソート） 作者: http://www.tokuyama.ac.jp/home/~kawamura/ TODO: 実装できないかもしれない。

DKC_EXTERN void WINAPI dkcQuickSort | ( | void * | base,
|  | size_t | num,
|  | size_t | width,
|  | DKC_SORT_COMPARE_TYPE | compare
| ) |

| いわいるクイックソートをする。(qsortを使いましょう＾＾； TODO: qsortのラッパーに終わるかもしれない。 dkcSort.c の 117 行で定義されています。
    00118 {
    00119     qsort(base,num,width,compare);
    00120 }

DKC_EXTERN void WINAPI dkcShellSort | ( | void * | base,
|  | size_t | num,
|  | size_t | width,
|  | DKC_SORT_COMPARE_TYPE | compare
| ) |

| いわいるシェルソートをする。 dkcSort.c の 16 行で定義されています。 参照先 BYTE, と dkcSwap().
    00016                                                                                            {
    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 }