#include <stdio.h>
#include <stdlib.h>
#include "counting_sort.h"

void counting_sort(int *array, int length){
    //YOUR CODE STARTS HERE
    //YOUR CODE STARTS HERE


    // Deklarien von Maximum und Minimum

    int min = array[0];
    int max = array[0];
    int i;


    // Bedingungen setzen
    for(i=0; i<length; i++){
        if (min>array[i])
            min = array[i];
        if(max<array[i])
            max = array[i];
    }

    // Größe der Liste
    int k = max - min +1;

    // Erstellen des Histrogramms
    int *histrogramm;
    histrogramm = (int*)calloc(k, sizeof(int));


    // Iteraieren der Liste

    for (int i = 0; i < length; i++ ){

        int p =array[i]- min;
        histrogramm [p]++;

    }

    // Durchlaufen der letzten Schleifen der Liste
    int h = 0;
    for (i=0; i < k ;i++){

        while(histrogramm[i]  < 0) {
            array[h] = i + min;
            histogram--;
        }

    }
    free(histrogramm);

    //YOUR CODE ENDS HERE

}