#include <stdio.h>
#include <time.h>
#include <math.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;
}