#include <stdio.h>

void countSort(int array[], int array_size) {

    int sorted_array[array_size];

    // calculate how many elements should be prepared
    int max = array[0];
    for(int i = 1; i < array_size; i++) {
        if(array[i] > max) {
            max = array[i];
        }
    }

    // prepare array for counting
    int count[max + 1];
    for (int i = 0; i < max + 1; i++) {
        count[i] = 0;
    }
    
    // couting
    for(int i = 0; i < array_size; i++) {
        count[array[i]]++;
    }

    // make a hash to output sorted index
    for (int i = 1; i < max + 1; i++) {
        count[i] += count[i - 1];
    }

    // sorting
    for (int i = 0; i < array_size; i++) {
        sorted_array[count[array[i]] - 1] = array[i];
        count[array[i]]--;
    }

    // copy sorted elements to the original array
    for (int i = 0; i < array_size; i++) {
        array[i] = sorted_array[i];
    }
}


int main (void) {

    int i;
    int array[10] = {3, 6, 1, 7, 2, 0, 4, 5, 9, 8};

    printf("       array: ");
    for (i = 0; i < sizeof(array) / sizeof(array[0]); i++) {
        printf("%d ", array[i]);
    }
    printf("\n");

    quickSort(array, 0, sizeof(array) / sizeof(array[0]) - 1);

    printf("sorted array: ");
    for (i = 0; i < sizeof(array) / sizeof(array[0]); i++) {
        printf("%d ", array[i]);
    }
    printf("\n");

    return 0;
}