// Пирамидальная сортировка (по возрастанию)
// Шамовцев, 2011
// реализация -  стыдно :)
#include <iostream>
#include <conio.h>
#include <time.h>

using namespace std;


void iswap(int &n1, int &n2)
{
    int temp = n1;
    n1 = n2;
    n2 = temp;
}

int getrandom(int &n)
{
    int random = 0;


    random = rand()%n;

    return random ;
}





int main()
{
    srand ( time(NULL) );


st:
    int  k,N = 0;
    cout << "Please input size"  ;
    cin >> N;
    int a[N];

    cout << "Lets generate our mass with size " <<N <<". Press Enter to continue" << endl;
    k = getch();
    if (k==13)



        for ( int i = 0; i < N; ++i )
        {
            a[i] = getrandom(N);

            cout << a[i] << " ";
        }


    clock_t t0 = clock();



    int sh = 0; //ñìåùåíèå
    bool b = false;
    for(;;)
    {
        b = false;
        for ( int i = 0; i < N; i++ )
        {
            if( i * 2 + 2 + sh < N )
            {
                if( ( a[i + sh] > /*<*/ a[i * 2 + 1 + sh] ) || ( a[i + sh] > /*<*/ a[i * 2 + 2 + sh] ) )
                {
                    if ( a[i * 2 + 1 + sh] < /*>*/ a[i * 2 + 2 + sh] )
                    {
                        iswap( a[i + sh], a[i * 2 + 1 + sh] );
                        b = true;
                    }
                    else if ( a[i * 2 + 2 + sh] < /*>*/ a[ i * 2 + 1 + sh])
                    {
                        iswap( a[ i + sh], a[i * 2 + 2 + sh]);
                        b = true;
                    }
                }
            }
            else if( i * 2 + 1 + sh < N )
            {
                if( a[i + sh] > /*<*/ a[ i * 2 + 1 + sh] )
                {
                    iswap( a[i + sh], a[i * 2 + 1 + sh] );
                    b = true;
                }
            }
        }
        if (!b) sh++;
        if ( sh + 2 == N ) break;
    }

    cout << endl << endl;


    clock_t t1 = clock();

    cout << "Lets watch our SORTED mass. Press Enter to continue" << endl;
    k = getch();
    if (k==13)
    {


        for ( int i = 0; i < N; ++i ) cout << a[i] << " ";
    }




    cout <<endl <<  "Elapsed time: " << (double)(t1 - t0) / CLOCKS_PER_SEC <<" ms"<< endl
         << "again? Press Enter, or any key to quit" << endl;
    k = getch();
    if (k==13)
    {
        goto st;
    }
    else

        _getch();
    return 0;
}