l7p1 SDA

//h
#ifndef             HEADER_H
#define             HEADER_H

#include<iostream>
#include<conio.h>
#include<ctime>
#include<time.h>

using namespace std;

#define max 10000001


void heapsort(int N,double v[]);
void Remove(int &N,double v[]);
void heapgen2(int N,double v[]);
void retro(int &N, double v[], int p);
void heapgen1(int N,double v[]);
void insert(int &N, double v[],double a);
void heapsort2(int N,double v[]);


#endif

//cpp

#include "header.h"
extern double v[max];
void insert(int &N, double v[],double a)
{
    v[++N]=a;
    int f,p;
    double aux;
    for(f=N;f>1;)
    {
        p=f>>1;//inseamna impartirea fiului la 2. este mai rapida ca impartirea normala
        if(v[f]>v[p])
        { aux=v[f];
        v[f]=v[p];
        v[p]=aux;
        f=p;
        }
        else
        {
            f=0;
        }
    }
}


void heapgen1(int N,double v[])   //generare heap folosind insertii;
{
    int i;
    for(i=1;i<N;)
        insert(i,v,v[i+1]);
}

void retro(int &N, double v[], int p)
{
    int f;
    double aux;
    while(p<<1<=N)
    {
        f=p<<1;
        if((f+1<=N)&&(v[f+1]>v[f]))
            ++f;
        if(v[p]<v[f])
        {
            aux=v[p];
            v[p]=v[f];
            v[f]=aux;
            p=f;
        }
        else
            p=N;
    }
}


void heapgen2(int N,double v[])  //generare heap folosin a doua metoda;
{
    int i;
    for(i=N>>1;i>1;i--)
        retro(N,v,i);
}


void Remove(int &N,double v[])
{
    double aux=v[1];
    v[1]=v[N];
    v[N--]=aux;
    retro(N,v,1);
}

void heapsort(int N,double v[])
{
    heapgen2(N,v);
    while(N>1)
    {
        Remove(N,v);
    }
}

void heapsort2(int N,double v[])
{
    heapgen1(N,v);
    while(N>1)
    {
        Remove(N,v);
    }
}

//main

#include "header.h"

double v[max];
int main()
{
    //double start,final;
    clock_t start,final,t,f;
    int n = max-1;
    for(int i=1;i<n;i++)
    {
        v[i]=i;
    }
    cout<<"values entered"<<endl;

    //system("PAUSE");

    cout<<"Clock started"<<endl;

    start=clock();
    heapsort(n,v);
    final=clock();
    cout<<"heapsort2"<<endl;
    cout<<double(final-start)/CLOCKS_PER_SEC<<endl;

    t=clock();
    heapsort2(n,v);
    f=clock();

    cout<<"Starting Heapsort 1..."<<endl;
    cout<<double(f-t)/CLOCKS_PER_SEC<<endl;

    system("PAUSE");

    return 0;
}