#include <stdio.h>
#include <time.h>
#include <math.h>
#include <stdlib.h>

void swap(int *xp, int *yp)
{
    int temp = *xp;
    *xp = *yp;
    *yp = temp;
}

void heapify(int arr[], int n, int i)
{
    int largest = i;
    int l = 2*i + 1;
    int r = 2*i + 2;

    if (l < n && arr[l] > arr[largest])
        largest = l;

    if (r < n && arr[r] > arr[largest])
        largest = r;

    if (largest != i)
    {
        swap(&arr[i], &arr[largest]);

        heapify(arr, n, largest);
    }
}

void heapSort(int arr[], int n)
{
    for (int i = n / 2 - 1; i >= 0; i--)
        heapify(arr, n, i);

    for (int i=n-1; i>=0; i--)
    {
        swap(&arr[0], &arr[i]);

        heapify(arr, i, 0);
    }
}

void countSort(int arr[],int n)
{

    int output[n], count[n+1], i;

    for(i = 0; arr[i]; ++i)
        ++count[arr[i]];

    for (i = 1; i <= n; ++i)
        count[i] += count[i-1];

    for (i = 0; arr[i]; ++i)
    {
        output[count[arr[i]]-1] = arr[i];
        --count[arr[i]];
    }

    for (i = 0; arr[i]; ++i)
        arr[i] = output[i];
}

int main(void) {
    int m;
    //clock_t czasStart,czasStop,Czas;
    m=100;
    int numbers[m];
    for (int i=0; i<m; i++){
            numbers[i]=(rand() % m);
    }

    //czasStart = clock();
    //czasStop = clock();
    //Czas=czasStop - czasStart;
    //printf("%d\n",CLOCKS_PER_SEC); milion jednostek na sekunde

    heapSort(numbers,m-1);
    countSort(numbers,m-1);

    for (int i=0; i<m; i++){
            printf("%d ",numbers[i]);
    }

    return 0;
}