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

void ShellSort(int *tab,int n)
{
    int i,j,h;
    int bufor;
    h = 1;
    while(h <= n)
    {
        h *= 3;
        h++;
    }
    while(h > 0)
    {
        for(i = h;i < n;i++)
        {
            j = i;
            bufor = tab[j];
            while(j >= h && tab[j-h] > bufor)
            {
                tab[j] = tab[j - h];
                j -= h;
            }
            tab[j] = bufor;
        }
        h/=3;
    }
}

void heapify(int *A,int l,int r)
{
    int i,j;
    int x;
    int isCorrect;
    x = A[l];
    i = l;
    j = 2 * i + 1;
    isCorrect = 0;
    while(j <= r && !isCorrect)
    {
        if(j < r &&A[j] < A[j+1])
           j++;
        if(x < A[j])
        {
            A[i] = A[j];
            i = j;
            j = 2 * i + 1;
        }
        else
            isCorrect = 1;
    }
    A[i] = x;
}

void buildHeap(int *A,int n)
{
    int i;
    for(i = n/2 - 1;i >= 0;i--)
        heapify(A,i,n - 1);
}

void heapSort(int *A,int n)
{
    int i;
    int x;
    buildHeap(A,n);
    for(i = n - 1; i >= 1;i--)
    {
        x = A[0];
        A[0] = A[i];
        A[i] = x;
        heapify(A,0,i - 1);
    }
}

int main(void) {
	// your code goes here
	int k,m,n;
	int *A;
	char esc;
	do
	{
	    printf("Podaj liczbe elementow tablicy \n");
	    scanf("%d", &n);
	    printf("Podaj gorny zakres przedzialu dla elementow tablicy \n");
	    scanf("%d", &m);
	    srand(time(NULL));
	    A = (int*)malloc(n*sizeof(int));
	    for(k = 0;k < n;k++)
	        A[k] = rand()%m;
	    for(k = 0;k < n;k++)
	       printf("%d ",A[k]);
	    printf("\n\n");
	    heapSort(A,n);
	    for(k = 0;k < n;k++)
	       printf("%d ",A[k]);
	    printf("\n\n");
	    free(A);
	    printf("Czy chcesz kontynuowac ? \n");
	    scanf(" %c",&esc);
	}
	while(esc != 'n');
	return 0;
}