実装したアルゴリズムたちの紹介
- 教科書でしかみない バブルソート
- バブルより効率が悪い ストゥージソート
- さらに効率が悪い スローソート
- 並列化していないバブルと同じ効率の悪い 奇偶転置ソート
- バブルよりマシで不安定な 選択ソート
- バブルよりマシで安定な 挿入ソート
- 挿入ソートとよく似ている ノームソート
- 挿入ソートの改良版な シェルソート
- バブルにシェルと同様の改造が施した コムソート
- タダの二本に枝分かれしていく木で作られた ツリーソート
- ツリーと選択が融合した ヒープソート
- ヒープソートの亜種な スムースソート
- 同じくヒープソートの亜種な デカルト木ソート
- 行ったり来たりな シェーカーソート
- 分類上は選択ソートの仲間な サイクルソート
- ある程度早い マージソート
- 大量なソートでは早い 基数ソート
- 基数と挿入の合わせ技 Proxmap sort
- インプレースな基数ソート アメリカンフラッグソート
- もっとも有名な クイックソート
コード
バブルソート
int bubble_sort(double *data,int size)
{
int i,j,k;
double tmp;
i = size - 1;
j = -1;
while(i && j) {
j = 0;
for(k=0;k<i;k++) {
if(data[k] > data[k+1]) {
tmp = data[k+1];
data[k+1] = data[k];
data[k] = tmp;
j = -1;
}
}
i--;
}
return 0;
}
ストゥージソート
void stooge_sort(double *data,int size)
{
int i;
double tmp;
if(size > 1 && data[0] > data[size-1]) {
tmp = data[0];
data[0] = data[size-1];
data[size-1] = tmp;
}
if(size >= 3) {
i = (2*size + 2)/3;
stooge_sort(data,i);
stooge_sort(data + size - i,i);
stooge_sort(data,i);
}
return;
}
スローソート
void slow_sort(double *data,int size)
{
int i;
double tmp;
if(size < 2) {
return;
}
i = (size-1)/2;
slow_sort(data,i+1);
slow_sort(data+i+1,size-i-1);
if(data[size-1] < data[i]) {
tmp = data[i];
data[i] = data[size-1];
data[size-1] = tmp;
}
slow_sort(data,size-1);
return;
}
奇偶転置ソート
void odd_even_sort(double *data,int size)
{
int i,j;
double tmp;
j=-1;
while(j) {
j=0;
for(i=0;i+1<size;i+=2) {
if(data[i] > data[i+1]) {
tmp = data[i];
data[i] = data[i+1];
data[i+1] = tmp;
j=-1;
}
}
for(i=1;i+1<size;i+=2) {
if(data[i] > data[i+1]) {
tmp = data[i];
data[i] = data[i+1];
data[i+1] = tmp;
j=-1;
}
}
}
return;
}
選択ソート
void selection_sort(double *data,int size)
{
int i,j,k;
double tmp;
for(i=0;i<size-1;i++) {
tmp = data[i];
k=i;
for(j=i+1;j<size;j++) {
if(tmp > data[j]) {
tmp = data[j];
k=j;
}
}
if(k != i) {
data[k] = data[i];
data[i] = tmp;
}
}
return;
}
挿入ソート
void insertion_sort(double *data,int size)
{
int i,j;
double tmp;
for(i=1;i<size;i++) {
tmp=data[i];
for(j=i;j>0 && data[j-1]>tmp;j--)
data[j]=data[j-1];
data[j] = tmp;
}
}
ノームソート
void gnome_sort(double *data,int size)
{
int i;
double tmp;
i=0;
while(i<size-1)
{
if(data[i] > data[i+1]) {
tmp = data[i];
data[i] = data[i+1];
data[i+1] = tmp;
if(i) {
i--;
}
} else {
i++;
}
}
return;
}
シェルソート
int shell_sort(double *data,int size)
{
int i,j,k;
int *a,ret_code;
double tmp;
ret_code = 0;
if(size <= 0) {
ret_code = -1;
goto error;
}
i=0;
j=1;
while(j<size) {
k = j;
while(k<size) {
i++;
k *= 3;
}
j *= 2;
}
if((a=(int *)malloc((i+2)*sizeof(int)))==NULL) {
ret_code = -1;
goto error;
}
a+=2;
i=0;
j=1;
while(j<size) {
k = j;
while(k<size) {
a[i++] = k;
k *= 3;
}
j *= 2;
}
a[-2]=i;
for(i=1;i<a[-2];i++) {
j=i;
while(j>0) {
k=(j-1)>>1;
if(a[j] > a[k]) {
a[-1] = a[j];
a[j] = a[k];
a[k] = a[-1];
} else {
break;
}
}
}
for(i=a[-2]-1;i>0;i--) {
a[-1] = a[i];
a[i] = a[0];
a[0] = a[-1];
j=0;
while(j*2+1<i) {
k=j*2+1;
if(k+1 < i && a[k] < a[k+1]) {
k++;
}
if(a[j] < a[k]) {
a[-1]=a[k];
a[k] = a[j];
a[j] = a[-1];
j=k;
} else {
break;
}
}
}
for(i=a[-2]-1;i>=0;i--) {
for(j=1;j<size;j++) {
tmp = data[j];
for(k=j;k-a[i]>=0 && data[k-a[i]]>tmp;k-=a[i]) {
data[k] = data[k-a[i]];
}
data[k] = tmp;
}
}
free(a-2);
error:
return ret_code;
}
コムソート
void comb_sort(double *data,int size)
{
int i,j,k;
double tmp;
j=size;
k=-1;
while(k) {
j=(10*j)/13;
if(j <= 1) {
j = 1;
k = 0;
}
for(i=0;i+j<size;i++) {
if(data[i] > data[i+j]) {
tmp = data[i];
data[i] = data[i+j];
data[i+j] = tmp;
k=-1;
}
}
}
return;
}
ツリーソート
int tree_sort(double *data,int size)
{
int i,j,k,l,ret_code;
double *a;
int *b;
ret_code = 0;
if((a = (double *)malloc(size*sizeof(double))) == NULL) {
ret_code = -1;
goto error01;
}
if((b = (int *)malloc(3*size*sizeof(int))) == NULL) {
ret_code = -1;
goto error02;
}
for(i=0;i<3*size;i++) {
b[i] = -1;
}
a[0] = data[0];
for(i=1;i<size;i++) {
j = 0;
while(j >= 0) {
if(a[j] > data[i]) {
l = 1;
} else {
l = 2;
}
k = j;
j = b[j*3 + l];
}
b[k*3 + l] = i;
b[i*3 + 0] = k;
a[i] = data[i];
}
i = 0;
j = -1;
k = 0;
while(i != -1) {
if(b[i*3 + 1] != -1 && j == b[i*3 + 0]) {
j = i;
i = b[i*3 + 1];
} else if(b[i*3 + 2] != -1 && j != b[i*3 + 2]) {
data[k++] = a[i];
j = i;
i = b[i*3 + 2];
} else {
if(j != b[i*3 + 2] || (b[i*3+1] == -1 && b[i*3+2] == -1)) {
data[k++] = a[i];
}
j = i;
i = b[i*3 + 0];
}
}
free(b);
error02:
free(a);
error01:
return ret_code;
}
ヒープソート
void heap_sort(double *data,int size)
{
int i,j,k;
double tmp;
for(i=1;i<size;i++) {
j = i;
while(j>0) {
k = (j-1)/2;
if(data[k] < data[j]) {
tmp = data[j];
data[j] = data[k];
data[k] = tmp;
j = k;
} else {
break;
}
}
}
for(i=size-1;i>=0;i--) {
tmp = data[i];
data[i] = data[0];
data[0] = tmp;
j = 0;
while(1) {
if(2*j + 1 >= i) {
break;
}
k = 2*j + 1;
if(k+1 < i && data[k] < data[k+1]) {
k++;
}
if(data[k] > data[j]) {
tmp = data[j];
data[j] = data[k];
data[k] = tmp;
j=k;
} else {
break;
}
}
}
return;
}
スムースソート
void repair_tree(double *tree,int tree_size,unsigned int *leonardo_number)
{
int i;
double tmp;
if(tree_size < 3) {
return;
}
i=1;
while(leonardo_number[i] < tree_size) i++;
if(tree[leonardo_number[i-1]-1] < tree[tree_size-2]) {
if(tree[tree_size-1] < tree[tree_size-2]) {
tmp = tree[tree_size-2];
tree[tree_size-2] = tree[tree_size-1];
tree[tree_size-1] = tmp;
repair_tree(tree + leonardo_number[i-1],leonardo_number[i-2],leonardo_number);
}
} else {
if(tree[tree_size-1] < tree[leonardo_number[i-1]-1]) {
tmp = tree[leonardo_number[i-1]-1];
tree[leonardo_number[i-1]-1] = tree[tree_size-1];
tree[tree_size-1] = tmp;
repair_tree(tree,leonardo_number[i-1],leonardo_number);
}
}
return;
}
int smooth_sort(double *data,int size)
{
int i,j,k,ret_code;
unsigned int *leonardo_number;
int *tree_size,*tree_offset;
double tmp;
ret_code = 0;
if(size < 1) {
ret_code = -1;
goto error01;
}
if((leonardo_number=(unsigned int *)malloc(3*64*sizeof(unsigned int)))==NULL) {
ret_code = -1;
goto error01;
}
tree_size = (int *)(leonardo_number + 64);
tree_offset = tree_size + 64;
leonardo_number[0] = 1;
leonardo_number[1] = 1;
i=2;
while(i<45) {
leonardo_number[i] = leonardo_number[i-1] + leonardo_number[i-2] + 1;
i++;
}
while(i<3*64) {
leonardo_number[i++] = 0;
}
tree_offset[0] = 0;
for(i=0;i<size;i++) {
j = 0;
while(tree_size[j]) j++;
tree_size[j]++;
k=0;
while(j>=2) {
while(leonardo_number[k] < tree_size[j] + tree_size[j-1] + tree_size[j-2]) k++;
if(leonardo_number[k] == tree_size[j] + tree_size[j-1] + tree_size[j-2]) {
tree_size[j] = 0;
tree_size[j-1] = 0;
tree_size[j-2] = leonardo_number[k];
j-=2;
} else {
j--;
}
}
j=0;
while(tree_size[j]) {
tree_offset[j+1] = tree_offset[j] + tree_size[j];
j++;
}
if(j >= 1) {
repair_tree(data+tree_offset[j-1],tree_size[j-1],leonardo_number);
}
}
j=1;
k=0;
while(tree_size[j]) {
if(data[tree_offset[j+1]-1] > data[tree_offset[k+1]-1]) {
k = j;
}
j++;
}
if(j != k+1) {
tmp = data[tree_offset[j]-1];
data[tree_offset[j]-1] = data[tree_offset[k+1]-1];
data[tree_offset[k+1]-1] = tmp;
repair_tree(data+tree_offset[j-1],tree_size[j-1],leonardo_number);
}
while(1) {
j = 0;
i = 0;
while(tree_size[j]) {
i += tree_size[j];
j++;
}
if(i <= 1) break;
j--;
i = 0;
while(leonardo_number[i] < tree_size[j]) i++;
if(i >= 2) {
tree_size[j] = leonardo_number[i-1];
tree_size[j+1] = leonardo_number[i-2];
} else {
tree_size[j]--;
}
j=0;
k=0;
while(tree_size[j]) {
tree_offset[j+1] = tree_offset[j] + tree_size[j];
if(data[tree_offset[j+1]-1] > data[tree_offset[k+1]-1]) {
k = j;
}
j++;
}
if(j != k+1) {
tmp = data[tree_offset[j]-1];
data[tree_offset[j]-1] = data[tree_offset[k+1]-1];
data[tree_offset[k+1]-1] = tmp;
}
j=0;
while(tree_size[j]) {
repair_tree(data+tree_offset[j],tree_size[j],leonardo_number);
j++;
}
}
free(leonardo_number);
error01:
return ret_code;
}
デカルト木ソート
int cartesian_tree_sort(double *data,int size)
{
int i,j,k,l,ret_code;
double *a;
int *b,*c;
ret_code = 0;
i = ((3 * size * sizeof(int) + sizeof(int) -1)/sizeof(double))*sizeof(double);
j = (i + sizeof(int) - 1)/sizeof(int);
if((a=(double *)malloc((j + size) * sizeof(int)))==NULL) {
ret_code = -1;
goto error01;
}
b = (int *)a;
c = b + j;
for(i=0;i<4*size;i++) {
b[i] = -1;
}
k=0;
for(i=1;i<size;i++) {
j = i-1;
while(b[3*j] != -1 && data[j] > data[i]) j=b[3*j];
if(data[j] > data[i]) {
k=i;
b[3*j] = i;
b[3*i+1] = j;
} else if(b[3*j+2] == -1) {
b[3*j+2] = i;
b[3*i] = j;
} else {
b[3*i] = j;
b[3*i+1] = b[3*j+2];
b[3*b[3*j+2]] = i;
b[3*j+2] = i;
}
}
i=0;
j=1;
c[i] = k;
while(i < size && c[i] != -1) {
k = b[3*c[i]+1];
if(k != -1) {
for(l=j;data[k] < data[c[l-1]];l--) {
c[l] = c[l-1];
}
c[l] = k;
j++;
}
k = b[3*c[i]+2];
if(k != -1) {
for(l=j;data[k] < data[c[l-1]];l--) {
c[l] = c[l-1];
}
c[l] = k;
j++;
}
i++;
}
for(i=0;i<size;i++) {
a[i] = data[i];
}
for(i=0;i<size;i++) {
data[i] = a[c[i]];
}
free(a);
error01:
return ret_code;
}
シェーカーソート
void cocktail_shaker_sort(double *data,int size)
{
int i,j,k,l;
double tmp;
i=0;
j=size-1;
l=-1;
while(l) {
l=0;
for(k=i;k<j;k++) {
if(data[k] > data[k+1]) {
tmp = data[k];
data[k] = data[k+1];
data[k+1] = tmp;
l=-1;
}
}
j--;
if(!l) {
break;
}
l=0;
for(k=j;k>i;k--) {
if(data[k] < data[k-1]) {
tmp = data[k];
data[k] = data[k-1];
data[k-1] = tmp;
l=-1;
}
}
i++;
}
return;
}
サイクルソート
void cycle_sort(double *data,int size)
{
int i,j,k;
double tmp;
i = 0;
while(i<size-1) {
tmp = data[i];
k=0;
j=i+1;
while(j<size) {
if(tmp > data[j++]) k++;
}
if(k) {
data[i] = data[i+k];
data[i+k] = tmp;
} else {
i++;
}
}
return;
}
マージソート(再帰版)
void merge_sort_c(double *a,double *b,int n,int m) {
int i,j,k,l;
double *c;
k = n >> 1;
if(n > 2) {
j = n - k;
merge_sort_c(a,b,k,m^0x01);
merge_sort_c(a+k,b+k,j,m^0x01);
} else if(m == 0) {
for(i=0;i<n;i++) {
b[i] = a[i];
}
}
if(m != 0) {
c = a;
a = b;
b = c;
}
i = 0;
j = k;
l = 0;
while(i<k && j<n) {
if(b[i] <= b[j]) {
a[l++] = b[i++];
} else {
a[l++] = b[j++];
}
}
while(i<k) {
a[l++] = b[i++];
}
while(j<n) {
a[l++] = b[j++];
}
}
int merge_sort(double *data,int size) {
double *tmp;
if((tmp = (double *)malloc(size*sizeof(double))) == NULL) {
return -1;
}
merge_sort_c(data,tmp,size,0);
free(tmp);
return 0;
}
マージソート(非再帰版)
int merge_sort(double *data,int size)
{
int i,j,k,l,m,n,m_max,n_max,ret_code;
double *tmp[2];
ret_code = 0;
tmp[0] = data;
if((tmp[1] = (double *)malloc(size*sizeof(double))) == NULL) {
ret_code = -1;
goto error01;
}
l = 0x00;
for(i=1;i<size;i*=2) {
for(j=0;j<size;j+=i*2) {
k = j;
m = j;
n = j + i;
m_max = (m+i < size)? m+i : size;
n_max = (n+i < size)? n+i : size;
while(m<m_max && n<n_max) {
if(tmp[l][m] <= tmp[l][n]) {
tmp[l^0x01][k++] = tmp[l][m++];
} else {
tmp[l^0x01][k++] = tmp[l][n++];
}
}
while(m<m_max) {
tmp[l^0x01][k++] = tmp[l][m++];
}
while(n<n_max) {
tmp[l^0x01][k++] = tmp[l][n++];
}
}
l ^= 0x01;
}
if(l == 0x01) {
for(i=0;i<size;i++) {
tmp[0][i] = tmp[1][i];
}
}
free(tmp[1]);
error01:
return ret_code;
}
基数ソート
int radix_sort(double *data,int size)
{
int i,j,k,ret_code;
double **a;
int **b;
unsigned char *c;
ret_code = 0;
if(size <= 1) {
ret_code = -1;
goto error;
}
i = 2*sizeof(double *);
i = ((i + sizeof(int *) - 1)/sizeof(int *));
i = (i +sizeof(double))*sizeof(int *);
i = ((i + sizeof(int) - 1)/sizeof(int));
i = (i + 257*sizeof(double))* sizeof(int);
i = ((i + sizeof(double) - 1)/sizeof(double));
i = (i+size) * sizeof(double);
if((a=(double **)malloc(i))==NULL) {
ret_code = -1;
goto error;
}
i = 2*sizeof(double *);
i = ((i + sizeof(int *) - 1)/sizeof(int *));
b = ((int **)a) + i;
i = (i +sizeof(double))*sizeof(int *);
i = ((i + sizeof(int) - 1)/sizeof(int));
b[0] = ((int *)a) + i;
i = (i + 257*sizeof(double))* sizeof(int);
i = ((i + sizeof(double) - 1)/sizeof(double));
a[1] = ((double *)a) + i;
a[0] = data;
for(i=1;i<sizeof(double);i++) {
b[i] = b[i-1] + 257;
}
for(i=0;i<257*sizeof(double);i++) {
b[0][i] = 0;
}
for(i=0;i<size;i++) {
c = (unsigned char *)(data + i);
if(c[sizeof(double)-1]&0x80) {
for(j=0;j<sizeof(double);j++) {
c[j] = ~c[j];
}
} else {
c[sizeof(double)-1] ^= 0x80;
}
for(j=0;j<sizeof(double);j++) {
b[j][1+c[j]]++;
}
}
k = 0x00;
for(i=0;i<sizeof(double);i++) {
for(j=0;j<256;j++) {
b[i][j+1] += b[i][j];
}
for(j=0;j<size;j++) {
c = (unsigned char *)(a[k] + j);
a[k^0x01][b[i][c[i]]] = a[k][j];
b[i][c[i]]++;
}
k ^= 0x01;
}
if(k==0x01) {
for(i=0;i<size;i++) {
data[i] = a[1][i];
}
}
for(i=0;i<size;i++) {
c = (unsigned char *)(data + i);
if(c[sizeof(double)-1]&0x80) {
c[sizeof(double)-1] ^= 0x80;
} else {
for(j=0;j<sizeof(double);j++) {
c[j] = ~c[j];
}
}
}
free(a);
error:
return ret_code;
}
Proxmap sort
unsigned int mapkey(double a)
{
uint64_t *b = (uint64_t *)&a;
*b = *b >> 52;
if((*b)&0x800) {
*b ^= 0xfff;
} else {
*b ^= 0x800;
}
return (unsigned int)*b;
}
int proxmap_sort(double *data,int size)
{
int i,j,k,ret_code;
double *a;
unsigned int *b,*c;
ret_code = 0;
k = (key_length > size)? key_length : size;
i = (((size + k)*sizeof(unsigned int) + sizeof(double) - 1)/sizeof(double))*sizeof(double);
j = i/sizeof(unsigned int);
i += size * sizeof(double);
if((b=(unsigned int *)malloc(i))==NULL) {
ret_code = -1;
goto error01;
}
c = b + k;
a = (double *)(b + j);
for(i=0;i<key_length;i++) {
b[i] = 0;
}
for(i=0;i<size;i++) {
c[i] = mapkey(data[i]);
b[c[i]]++;
}
j = 0;
for(i=0;i<key_length;i++) {
k = b[i];
b[i] = j;
j += k;
}
for(i=0;i<size;i++) {
c[i] = b[c[i]];
}
for(i=0;i<size;i++) {
b[i] = 0;
}
for(i=0;i<size;i++) {
j = c[i];
while(b[j] && data[i] >= a[j]) j++;
if(!b[j]) {
b[j] = -1;
a[j] = data[i];
} else {
k = j + 1;
while(b[k]) k++;
b[k] = -1;
while(k > j) {
a[k] = a[k-1];
k--;
}
a[j] = data[i];
}
}
for(i=0;i<size;i++) {
data[i] = a[i];
}
free(b);
error01:
return ret_code;
}
アメリカンフラッグソート(再帰版)
void american_flag_sort_c(double *data,int size,int **a,int l)
{
int i,j;
unsigned char *b;
double tmp;
if(l==0|| size < 1) {
return;
}
l--;
for(i=0;i<257;i++) {
a[l][i] = 0;
}
for(i=0;i<size;i++) {
b = (unsigned char *)(data + i);
a[l][1+b[l]]++;
}
for(i=0;i<256;i++) {
a[l][i+1] += a[l][i];
a[sizeof(double)][i] = a[l][i+1];
}
b = (unsigned char *)&tmp;
for(i=0;i<256;i++) {
for(j=a[l][i];j<a[sizeof(double)][i];) {
tmp = data[j];
if(b[l] != i) {
data[j] = data[a[l][b[l]]];
data[a[l][b[l]]] = tmp;
} else {
j++;
}
a[l][b[l]]++;
}
}
a[l][0] = 0;
for(i=0;i<256;i++) {
a[l][i+1] = a[sizeof(double)][i];
}
for(i=0;i<256;i++) {
american_flag_sort_c(data+a[l][i],a[l][i+1]-a[l][i],a,l);
}
return;
}
int american_flag_sort(double *data,int size)
{
int i,j,ret_code;
int *a[1+sizeof(double)];
unsigned char *b;
ret_code = 0;
if((a[0]=(int *)malloc(1024*(1+sizeof(double))*sizeof(int)))==NULL) {
ret_code = -1;
goto error01;
}
for(i=1;i<=sizeof(double);i++) {
a[i] = a[i-1] + 1024;
}
for(i=0;i<size;i++) {
b = (unsigned char *)(data + i);
if(0x80 & b[sizeof(double)-1]) {
for(j=0;j<sizeof(double);j++) {
b[j] = ~b[j];
}
} else {
b[sizeof(double)-1] ^= 0x80;
}
}
american_flag_sort_c(data,size,a,sizeof(double));
for(i=0;i<size;i++) {
b = (unsigned char *)(data + i);
if(0x80 & b[sizeof(double)-1]) {
b[sizeof(double)-1] ^= 0x80;
} else {
for(j=0;j<sizeof(double);j++) {
b[j] = ~b[j];
}
}
}
free(a[0]);
error01:
return ret_code;
}
アメリカンフラッグソート(非再帰版)
int american_flag_sort(double *data,int size)
{
int i,j,k,ret_code;
int **a,*b;
double **c;
unsigned char *d;
double tmp;
ret_code = 0;
i = (1+sizeof(double))*sizeof(int *);
i = ((i + sizeof(double *) - 1)/sizeof(double *))*sizeof(double *);
i += sizeof(double)*sizeof(double *);
i = ((i + sizeof(int) -1)/sizeof(int))*sizeof(int);
i += 257*(1+sizeof(double))*sizeof(int);
i += 2*sizeof(double)*sizeof(int);
if((a=(int **)malloc(i))==NULL) {
ret_code = -1;
goto error01;
}
i = (1+sizeof(double))*sizeof(int *);
j = (i + sizeof(double *) - 1)/sizeof(double *);
i = j * sizeof(double *);
c = ((double **)a) + j;
i += sizeof(double)*sizeof(double *);
j = (i + sizeof(int) -1)/sizeof(int);
a[0] = ((int *)c) + j;
for(i=1;i<=sizeof(double);i++) {
a[i] = a[i-1] + 257;
}
b = a[sizeof(double)] + 257;
for(i=0;i<size;i++) {
d = (unsigned char *)(data + i);
if(0x80 & d[sizeof(double)-1]) {
for(j=0;j<sizeof(double);j++) {
d[j] = ~d[j];
}
} else {
d[sizeof(double)-1] ^= 0x80;
}
}
b[sizeof(double)-1] = size;
b[2*sizeof(double)-1] = 0;
c[sizeof(double)-1] = data;
i=sizeof(double)-1;
while(1) {
for(j=0;j<257;j++) {
a[i][j] = 0;
}
for(j=0;j<b[i];j++) {
d = (unsigned char *)(c[i] + j);
a[i][1+d[i]]++;
}
for(j=0;j<256;j++) {
a[i][j+1] += a[i][j];
a[sizeof(double)][j] = a[i][j+1];
}
d = (unsigned char *)(&tmp);
for(j=0;j<256;j++) {
for(k=a[i][j];k<a[sizeof(double)][j];) {
tmp = c[i][k];
if(j != d[i]) {
c[i][k] = c[i][a[i][d[i]]];
c[i][a[i][d[i]]] = tmp;
} else {
k++;
}
a[i][d[i]]++;
}
}
a[i][0] = 0;
for(j=0;j<256;j++) {
a[i][j+1] = a[sizeof(double)][j];
}
k = 0;
if(i != 0 && b[i]>1) {
k = 0;
while(a[i][1+k] - a[i][k] == 0 && k < 256) k++;
if(k < 256) {
c[i-1] = c[i] + a[i][k];
b[i-1] = a[i][1+k] - a[i][k];
b[sizeof(double)+i] = k+1;
k=0;
i--;
} else {
k=1;
}
} else {
k = 1;
}
if(k) {
j = i+1;
while(j<sizeof(double)) {
k = b[sizeof(double)+j];
while(a[j][1+k] - a[j][k] == 0 && k < 256) {
k++;
}
if(k == 256) {
b[sizeof(double)+j] = 256;
j++;
} else {
break;
}
}
if(j==sizeof(double)) {
goto end;
}
c[j-1] = c[j] + a[j][k];
b[j-1] = a[j][1+k] - a[j][k];
b[sizeof(double)+j] = k + 1;
i=j-1;
}
}
end:
for(i=0;i<size;i++) {
d = (unsigned char *)(data + i);
if(0x80 & d[sizeof(double)-1]) {
d[sizeof(double)-1] ^= 0x80;
} else {
for(j=0;j<sizeof(double);j++) {
d[j] = ~d[j];
}
}
}
free(a);
error01:
return ret_code;
}
クイックソート(再帰版)
void quick_sort(double *a,int size)
{
int i,j;
double p,q;
if(size >= 3) {
if(a[0] < a[size/2]) {
if(a[size/2] < a[size-1]) {
p = a[size/2];
} else if (a[size-1] < a[0]){
p = a[0];
} else {
p = a[size-1];
}
} else {
if(a[size/2] > a[size-1]) {
p = a[size/2];
} else if (a[size-1] > a[0]){
p = a[0];
} else {
p = a[size-1];
}
}
} else if(size == 2) {
p = a[0];
} else {
return;
}
i = 0;
j = size -1;
while(1) {
while(a[i] < p) i++;
while(a[j] > p) j--;
if(i>=j) break;
q = a[i];
a[i] = a[j];
a[j] = q;
i++;
j--;
}
quick_sort(a,i);
j++;
i = size - j;
quick_sort(a+j,i);
return;
}
クイックソート(非再帰版)
int quick_sort(double *a,int size)
{
int i,j,k;
double p,q;
int *stack;
if((stack = (int *)malloc(16*sizeof(int)*sizeof(int))) == NULL) {
return 0;
}
stack[0] = 0;
stack[1] = size;
i = 0;
while(i>=0) {
if(stack[i*2+1] - stack[i*2+0] >= 3) {
k = (stack[i*2+1] + stack[i*2+0])/2;
if(a[stack[i*2+0]] < a[k]) {
if(a[k] < a[stack[i*2+1]-1]) {
p = a[k];
} else if(a[stack[i*2+0]] < a[stack[i*2+1]-1]) {
p = a[stack[i*2+1]-1];
} else {
p = a[stack[i*2+0]];
}
} else {
if(a[k] > a[stack[i*2+1]-1]) {
p = a[k];
} else if(a[stack[i*2+0]] < a[stack[i*2+1]-1]) {
p = a[stack[i*2+0]];
} else {
p = a[stack[i*2+1]-1];
}
}
} else if(stack[i*2+1] - stack[i*2+0] == 2) {
p = a[stack[i*2+0]];
} else {
i--;
continue;
}
j = stack[i*2+0];
k = stack[i*2+1] -1;
while(1) {
while(a[j] < p) j++;
while(a[k] > p) k--;
if(j>=k) break;
q = a[j];
a[j] = a[k];
a[k] = q;
j++;
k--;
}
if(j - stack[i*2+0] < stack[i*2+1] - k - 1) {
stack[i*2+2] = stack[i*2+0];
stack[i*2+3] = j;
stack[i*2+0] = k+1;
} else {
stack[i*2+2] = k+1;
stack[i*2+3] = stack[i*2+1];
stack[i*2+1] = j;
}
i++;
}
free(stack);
return 0;
}
プログラミングの難易度
スムースソート > 非再帰アメリカンフラッグソート > その他
ヒープソートが簡単だったので舐めてかかったら意外と難しかった
扱い易さ
非再帰マージソート > ヒープソート > その他
クイックソートは再帰だとスタック消費量が恐ろしいかといって非再帰だと面倒
簡単な挿入ソートは計算オーダが $ O(n^2) $ で遅すぎる
ある程度簡単でそれなりに速くなおかつ非再帰なソート $ = $ とっても扱いやすい