SDA L7

//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;
}