/*

Algoritmi de sortare

[1] Bubble Sort
[2] Select Sort
[3] Counter Sort
[4]  Shell Sort
----------------------
*/
#include<iostream>
#include<cstdlib>
#include<time.h>

using namespace std;

int n;
int V[1000];

int init_data()
{
srand(time(0));   // seed randomize " pornim motorul " !
do { n=rand()%10; } while (n==0);
for(int i=1;i<=n;i++) V[i]=rand()%100;
}

int print_data()
{
cout<<" Elements : "<<n<<endl;
for(int  i=1;i<=n;i++) cout<<V[i]<<" ";
}

int sort_data()
{
/*
Heap Sort :
Lucreaza reorganizand vectorul ca heap de n-1 ori

pas i=1  de la 1 la n organizez heap
pas i=2 de la 2 la n organizez heap
...
pas n-1 de la n-1 la n organizez heap

Unde :  Prin heap intelegem o structura de tip arbore binar
in care fiecare nod are un nume si detine o informatie astfel incat

[1] Daca nodul i are descendenti acestia se numesc 2*i si 2*i+1
[2] Informatia nodului i este >= informatia descendentilor lui

542 233 144

Exemplu Fie n=5 si heapul

             1 [ 543 ]
               /     \
      2 [233]      3 [144]
      /        \
 4[104]      5 [73]

Acest heap se poate reprezenta sub forma de vector

              788

  --------------------
 |  788   |   543  |  144  |  233
   ---------------------------------
    1              2          3           4

Obs : Intr-un heap ( root oriented  )  informatia maxima este in radacina

Constructia unui heap  :

1.  Pornim cu heapul singleton

La un pas arbitrar k inseram un al k-lea element in heap

Element k are tata |k/2| !!!

 --------------------
 |  543   |   233   |
   ---------------------
     1              2


*/
}

int main()
{
init_data();
cout<<"Initial  ";
print_data();
sort_data();
cout<<endl<<"Final  ";
print_data();
}