A)

Implementirajte 2 verzije HeapSort algoritma koristeći rekurzivnu i iterativnu verziju funkcije Heapify.

Pseudokod


Heapify(array A,int i,int m);
    l=2*i+1
    r=2*i+2
    max=i
    if(l<=m and A[l]>A[max])
        max=l
    if(r<=m and A[r]>A[max])
        max=r
    if(max!=i)
        swap A[i] with A[max]
        Heapify(A,max,m)

Heapify2(array A,int i,int m)
    max=i
    while(max<=m)
        l=2*max+1
        r=2*max+2
        i=max
        if(l<=m and A[l]>A[i])
            max=l
        else
            max=i
        if(r<=m and A[r]>A[max])
            max=r
        if (i!=max)
            Swap A[i] with A[max]
        else
            return

 
BuildHeap(int n,array A[1..n])
    for i=n/2 to 1
        Heapify(A,i,n)

HeapSort(int n,array A[1..n])
    BuildHeap(n,A)
    m=n
    while(m>=2)
        swap A[1] with A[m]
        m=m-1;
        Heapify(A,1,m)
 

B)

Pokrenite iterativnu i rekurzivnu verziju heap sorta za npr. 3000000 elemenata te ispišite njihova vremena izvršavanja. Koja verzija je brža?

Implementirajte bubble sort te ispišite njegovo vrijeme izvršavanja za npr. 50000 elemenata.

Za  vrijeme izvršavanja korisitite funkciju

int GetTickCount(void);

koja vraća koliko milisekundi je prošlo od trenutka  pokretanja sustava.

Npr:

vrijeme1=GetTickCount();

HeapSort(size-1,A);

vrijeme2= GetTickCount();

Vrijeme izvršavanja Heap sorta je: vrijeme2-vrijeme1

Pseudokod za bubble sort:

for i=0 to size-1

            for j=i+1 to size

                        if(A[i]>A[j])

                                   Swap(A[i],A[j])

start.cpp

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


int fast=0;


void Swap(int A[],int i, int j)
{
    int temp;
    temp=A[i];
    A[i]=A[j];
    A[j]=temp;
}

void Heapify(int A[],int i,int m)
{
    int max,l,r;
    l=2*i+1;
    r=2*i+2;
    max=i;
    if((l<=m)&&(A[l]>A[max]))
            max=l;
    if((r<=m)&&(A[r]>A[max]))
            max=r;
    if(max!=i)
    {
            Swap(A,i,max);
            Heapify(A,max,m);
    }
}
void Heapify2(int A[],int i,int m)
{
    int l,r;
    int max=i;

    while ( max <=m )
    {
            l=2*max+1;
            r=2*max+2;
            i=max;

            if ((l <= m) && (A[l] > A[i]))
                    max=l;

            if ((r <= m) && (A[r] > A[max]))
                    max=r;
            if (max != i)
                    Swap (A,i,max);
            else
                    return;
       }
}


void BuildHeap(int n,int A[])
{
        int i;
        for (i=n/2;i>=0;i--)
                if (fast==0)
                    Heapify(A,i,n-1);
                else
                    Heapify2(A,i,n-1);
}

void HeapSort(int n,int A[])
{
        int m,temp;
        BuildHeap(n,A);
        m=n;
        while(m>=1)
        {
                temp=A[0];
                A[0]=A[m];
                A[m]=temp;
                m=m-1;
             if (fast==0)
                    Heapify(A,0,m);
            else
                    Heapify2(A,0,m);
           }
}

void BubbleSort(int size,int A[])
{

// implementirajte bubble sort
}


int main()
{

    FILE *file1,*file2;
    char c;
    int vrijeme1,vrijeme2,i,size;


    printf("0)rekurzivno\n1)iterativno\n");
    scanf(" %d",&fast);

    printf("Unesi velicinu niza\n");
    scanf(" %d", &size);

    int *A=(int*)malloc(size*sizeof(int));
    for(i=0;i<size;i++)
            A[i]=rand();

    //pokreni heap sort, ispiši vrijeme sortiranja



    printf("vrijeme je %d\n",vrijeme2-vrijeme1);

    file1 = fopen( "OutputHeap.txt", "w" );
    for(i=0;i<size;i=i++)
            fprintf(file1, "%d\n",A[i]);
    fclose(file1);


    for(i=0;i<size;i++)
            A[i]=rand();

    printf("BubbleSort?(y/n)\n");
    c=getch();
    if(c=='y')
    {
                //pokreni bubble sort i ispiši njegovo vrijeme izvršavanja


            file2 = fopen( "OutputBubble.txt", "w" );
            for(i=0;i<size;i=i++)
            fprintf(file2, "%d\n",A[i]);
            fclose(file2);
    }
    free(A);   
    return 0;

}