ソートアルゴリズム20種をCで作ってみた

##実装したアルゴリズムたちの紹介

• 教科書でしかみない バブルソート
• バブルより効率が悪い ストゥージソート
• さらに効率が悪い スローソート
• 並列化していないバブルと同じ効率の悪い 奇偶転置ソート
• バブルよりマシで不安定な 選択ソート
• バブルよりマシで安定な 挿入ソート
• 挿入ソートとよく似ている ノームソート
• 挿入ソートの改良版な シェルソート
• バブルにシェルと同様の改造が施した コムソート
• タダの二本に枝分かれしていく木で作られた ツリーソート
• ツリーと選択が融合した ヒープソート
• ヒープソートの亜種な スムースソート
• 同じくヒープソートの亜種な デカルト木ソート
• 行ったり来たりな シェーカーソート
• 分類上は選択ソートの仲間な サイクルソート
• ある程度早い マージソート
• 大量なソートでは早い 基数ソート
• 基数と挿入の合わせ技 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) $ で遅すぎる

ある程度簡単でそれなりに速くなおかつ非再帰なソート $ = $ とっても扱いやすい