#include<stdio.h>
#include<conio.h>
#include<windows.h>

#define N 100

int a[N], i, j, x, l, p;

//----------------------------------------
void przesiewanie(int l, int  p){
    i = l;
    j = 2*i;
    x = a[i];
    while(j<=p){
        if(j<p){
            if(a[j] < a[j+1]){
                j = j+1;
            }
        }
        if(x>=a[j]){
            goto me;
        }
        a[i] = a[j];
        i=j;
        j=2*i;
    }
    me:
        a[i] = x;
}


void heapsort(){

    l = (N/2)+1;
    p = N-1;
    while(l>0){
        l = l-1;
        przesiewanie(l, p);
    }

    while(p>0){
        x = a[0];
        a[0] = a[p];
        a[p] = x;
        p = p-1;
        przesiewanie(l, p);
    }
}
//--------------------------------------

double GetTime()
{
  long long f,t;
  QueryPerformanceFrequency((PLARGE_INTEGER)&f);
  QueryPerformanceCounter((PLARGE_INTEGER)&t);
  return (double)t/(double)f;
}


int main(){
    //------LOSOWY-------------------
    srand(time(NULL));
    for(i=0; i<N; i++) a[i] = rand();
    double one=GetTime();
    heapsort();
    double two=GetTime();
    printf("Losowy: \t%lf\n", (double)(two-one));
    //--------------------------------


    //-------CIAG-STALY---------------
    for(i=0; i<N; i++) a[i] = 3;
    one=GetTime();
    heapsort();
    two=GetTime();
    printf("Ciag staly: \t%lf\n", (double)(two-one));
    //--------------------------------


    //----------CIAG-ROSNACY----------
    for(i=0; i<N; i++) a[i] = i+1;
    one=GetTime();
    heapsort();
    two=GetTime();
    printf("Ciag rosnacy: \t%lf\n", (double)(two-one));
    //--------------------------------


    //----------CIAG-MALEJACY----------
    j=8;
    for(i=0; i<N; i++){
      a[i] = j;
      j--;
    }
    one=GetTime();
    heapsort();
    two=GetTime();
    printf("%d\n\n", a[0]);
    for(i=0; i<N; i++) printf("%d\t", a[i]);
    printf("Ciag malejacy: \t%lf\n", (double)(two-one));
    //---------------------------------


    //for(i=0; i<N-1; i++) if(a[i] > a[i+1]){ printf("Nie jest posortowany"); break;}
    //for(i=0; i<N; i++) printf("[%d]: %d\t", i, a[i]);

    getch();
    return 0;
}