#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_) |
dkcSort.h で定義されています。
|
|
|
いわいるバイトニックソートをする。
|
|
いわゆるバブルソートをする。 参照元 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 }
|
|
いわいるコムソートをする。 参照先 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 }
|
|
参照先 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 }
|
|
Distribution count sort 分布数えソート。大量の記憶領域を使うがO(n)で極速! しかし、仮想記憶上ではほぼ意味無しか!?
参照先 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 }
|
|
参照先 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 }
|
|
いわいるマルチパーテーションソート(多重分割ソート)
|
|
いわいるクイックソートをする。(qsortを使いましょう^^;
|
|
いわいるシェルソートをする。 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 }
|