#include <stdio.h>

/* キーは0からMまでの範囲の整数 */
#define  M   10

void counting_sort(int a[], int b[], int n);
void print_data(int data[], int array_length);

/* ソートするデータ */
int src_data[] = {8,4,10,3,8,5};
#define N sizeof(src_data) / sizeof(src_data[0]) /* 要素素 */

/* 作業用配列 */
int work_data[N-1];

/* キーの分布を数え上げるための配列 */
int count[M+1];

int main(int argc, char **argv)
{
    printf("unsorted:\n");
    print_data(src_data, N);

    /* counting sort */
    counting_sort(src_data, work_data, N);

    printf("sorted:\n");
    print_data(work_data, N);
    return 0;
}

/* 大きさnの配列aを分布数え上げソートによって整列する。
 *    結果は配列bに得られる */
void counting_sort(int a[], int b[], int n)
{
    int  i;

    /* カウンタをすべて0にする */
    for (i = 0; i <= M; i++)
        count[i] = 0;

    /* キーを数え上げる */
    for (i = 0; i < n; i++)
        count[a[i]]++;

    /* 数え上げたキーの累積度数分布を求める */
    for (i = 0; i < M; i++) {
        count[i+1] += count[i];
    }

    /* 度数分布に従ってデータを配列aから配列bにコピーする */
    for (i = n - 1; i >= 0; i--) {
        b[--count[a[i]]] = a[i];
    }
}

void print_data(int data[], int array_length)
{
    int i;
    for (i = 0; i < array_length; i++) {
        printf("%d\n", data[i]);
    }
}