#include <iostream>
#include <conio>
#include <math>              // log ()
#include <stdlib>            // exit ()
int wielkoscTablicy;
int *tab;

// zmien Wielkosc ()
void zmienWielkosc(void)
{
cout << "Wielkosc tablicy : ";
cin >> wielkoscTablicy;
}

// wyswietl ()
void wyswietl(void)
{
for (int i = 0; i < wielkoscTablicy; i++)
  cout << tab[i] << " ";
}

// czekaj ()
void czekaj(void)
{
getch();
}

// losowaTablica ()
void losowaTablica(void)
{
int losujDo, blad = 0;

do
  {
  cout << "Losuj do : ";
  cin >> losujDo;
  if (losujDo < 1)
    {
    blad++;
    cout << "\n\nTa liczba powinna byc wieksza od 1\n";
    }
  }
while (losujDo < 1);
for (int i = 0; i < wielkoscTablicy; i++)
  {
  tab[i] = random(losujDo);
  cout << tab[i] << " ";
  }
}

// wysokoscStogu () -> wysokosc ( wielkosc tablicy )
int wysokoscStogu(int wielkoscTablicy)
{
return log(wielkoscTablicy + 1) / log(2);
}

// poprzednik () -> poprzednik ( nastepnik )
int poprzednik(int nastepnik)
{
return (nastepnik - 1) / 2;
}


// przesiewanie()
int przesiewanie(int wielkoscTablicy)
{
if (wielkoscTablicy == 0)    // warunek wyjscia z rekurencji
return tab[0];
else
  {
  for (int i = (wielkoscTablicy - 1); i > 0; i--) // sprawda tablice od ostatniego elementu
    {
    if (tab[i] >= tab[poprzednik(i)]) // nastepnik >= poprzednika -> ZAMIANA
      {
      int temp;

      temp = tab[poprzednik(i)];
      tab[poprzednik(i)] = tab[i];
      tab[i] = temp;
      }                      // if
    }                        // for
  int temp;                  // zamienia element pierwszy

  // ( najwiekszy ) z ostatnim

  temp = tab[wielkoscTablicy - 1];
  tab[wielkoscTablicy - 1] = tab[0];
  tab[0] = temp;
  return przesiewanie(wielkoscTablicy - 1);
  }                          // else
}

// main()
void main(void)
{
//----------------- wywolywane tylko raz - przy starcie
zmienWielkosc();
tab = new int[wielkoscTablicy];

losowaTablica();
wyswietl();
czekaj();

// sortowanie rosnace
clrscr();
cout << "Wysokosc stogu : " << wysokoscStogu(wielkoscTablicy) << "\n\n";
cout << "Tablica do posortowania :\n\n";
wyswietl();
cout << "\n\nTablica posortowana rosnaco :\n\n";
przesiewanie(wielkoscTablicy);
wyswietl();
czekaj();
}                            // koniec