#include<iostream>
#include <algorithm>
#include<ctime>
using namespace std;

void buble(int *tab,int n) //sorotwanie babelkowe funkcja dostaje tablice przez wskaznik i jej rozmiar
{
    int tmp; // zmienna pomocniczka do zamiany kolejnosci
    for(int i=0; i<n-1; i++) //blblalblbablabl reszta jebnaych komentarzy
    {
        for(int j=0; j<n-1-i; j++)
        {
            if( tab[j] > tab[j+1])
            {
                tmp = tab[j];
                tab[j] = tab[j+1];
                tab[j+1] = tmp;

            }
        }
    }
}
void insert(int *tab, int n)
{
    int tmp;
    for(int i = 1,j ; i<n; i++)
    {
        tmp = tab[i];
        for( j = i - 1; j >=0 && tmp <tab[j]; --j)
            tab[j+1] = tab[j];
        tab[j + 1] = tmp;
    }
}
void heapify(int *T,int n, int i)
{
    int l,r;
    l = 2*i;
    r = 2*i+1;
    int largest = i;
    if( (l<=n) && (T[l] > T[i]) )
        largest = l;
    if( (r<=n) && (T[r] > T[largest]) )
        largest = r;

    if(largest != i)
    {
        swap(T[i], T[largest]);
        heapify(T,n,largest);
    }
}
void BuildHeap(int *T, int n)
{
    for( int i=n/2; i>=0; --i)
        heapify(T, n, i);
}
void HeapSort(int *T, int n)
{
    BuildHeap(T, n);
        for(int i=n-1; i>0; --i)
        {
            swap(T[0], T[i]); //element przenisimy na koniec
            heapify(T, --n, 1); //przywracamy wlasnosc dla kopca mniejszego
        }
}
int main()
{
    const int S = 10;
    int tab[S];
    srand(static_cast<unsigned int>(time(NULL)));
    for(int i=0; i<S; i++)
        tab[i] = rand()%10;

    cout << "tablica nieposotowana: " << endl;
    for(int i=0; i<S; i++)
        cout << tab[i] << "   ";
    cout << endl;

    HeapSort(tab, S);

    cout << "tablica posortowana: " << endl;
    for(int i=0; i<S; i++)
        cout << tab[i] << "   ";
    return 0;
}