qsort を用いたソート(C アルゴリズム)

Ｃ言語の標準関数である qsort() 関数を用いない qsort の例です。入力データは重複無の乱数を用いています。ソートされた結果は0から乱数の最大数までの昇順の数になります。

qsort を用いたソート(C アルゴリズム)(list_52.c) 
//-----------------------------------------------------------------
// クイックソート: list_52.c
//-----------------------------------------------------------------
#include <stdio.h>
#include <time.h>

#define MAX 10 // データの個数

//-----------------------------------------------------------------
int  rintv(double value);
void noduplex_rand(int n,int *a);
int  random(int max,unsigned long* idum);
void display(int* a, int n);
void quick_sort(int* a, int n);
//-----------------------------------------------------------------

int main()
{
    int a[MAX];
    noduplex_rand(MAX,a);
    printf("**before quick sort\n");
    display(a, MAX);
    quick_sort(a, MAX);
    printf("**after quick sort\n");
    display(a, MAX);
    return 0;
}

// double -> int
int rintv(double value)
{
    if(value > 0) return (int)(value + 0.5);
    else          return (int)(value - 0.5);
}
// 0〜max までの乱数の発生(int型)
int random(int max,unsigned long* idum)
{
    *idum=(*idum)*1103515245 + 12345;
    return rintv(max * ((double)(*idum/65536 % 32768) / (double)32767));
}

// 重複無の乱数発生
void noduplex_rand(int n,int *a)
{
    unsigned long idum;
    int i,rn,val;
    int *rand_tbl=(int*)calloc(n,sizeof(int)); /* 変換テーブル */
    int *hist=(int*)calloc(n,sizeof(int));
    /* 乱数発生のための変数の初期化 */
    idum = time(NULL);
    /* 変換テーブル準備 */
    for(i=0;i<n;i++) rand_tbl[i] = i;
    /* 重複無乱数の発生 */
    memset(hist,0,sizeof(int)*n);
    rn = n-1;
    while(rn!=-1){
        val = random(rn,&idum);
        hist[rand_tbl[val]]++;
        a[n-rn-1] = rand_tbl[val];
        /* valが入ったところを詰めて、変換テーブルの変更 */
        for(i=val;i<rn;i++) rand_tbl[i] = rand_tbl[i+1];
        rn --;
    }
    free(rand_tbl);
    free(hist);
}

// 表示
void display(int* a, int n)
{
    int k;
    printf(" ");
    for(k=0;k<n;k++) printf("%d ", a[k]);
    printf("\n");
}

void quick_sort(int* a, int n)
{
    int i,j,b;
    if(n<=1) return;
    b = a[(n-1) >> 1];
    i = 0;
    j = n - 1;
    while(i<=j) {
        while(a[i]< b) i++;
        while(a[j]> b) j--;
        if(i<=j){
            int w = a[i];
            a[i++] = a[j];
            a[j--] = w;
        }
    }
    quick_sort(a,i);
    quick_sort(a+i,n-i);
}


Gami[352]% ./list_52.exe
**before quick sort
 3 5 1 7 8 2 9 0 6 4
**after quick sort
 0 1 2 3 4 5 6 7 8 9
Gami[353]%
inserted by FC2 system