Write a program to sort a given set of elements with the Heap sort.

1) Repeat the experiment for different values of n = 20000,50000, 100000, 500000 and report the time (in seconds) required to sort the elements.

2)For each of aforementioned case, consider arrays as random,sorted, and reverse-sorted and observe running time variation for different types of input for heap sort.

Note: No keyboard input. Use Random number generator.

Code

 
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
void show(int *A, int n)
{
    for (int i = 0; i < n; i++)
        printf("%d ", A[i]);
}
void swap(int *a, int *b)
{
    int t = *a;
    *a = *b;
    *b = t;
}
void heapify(int A[], int n, int i)
{
    int largest = i;
    int l = 2 * i + 1;
    int r = 2 * i + 2;

    if (l < n && A[l] > A[largest])
        largest = l;

    if (r < n && A[r] > A[largest])
        largest = r;

    if (largest != i)
    {
        swap(&A[i], &A[largest]);

        heapify(A, n, largest);
    }
}

void heapSort(int A[], int n)
{
    for (int i = n / 2 - 1; i >= 0; i--)
        heapify(A, n, i);

    for (int i = n - 1; i > 0; i--)
    {

        swap(&A[0], &A[i]);
        heapify(A, i, 0);
    }
}

int main()
{
    double time_spent;

    int B[4] = {20000, 50000, 100000, 500000};
    printf("\nFor random array:\n ");
    for (int j = 0; j < 4; j++)
    {
        printf("For n=%d: ", B[j]);
        clock_t begin = clock();
        srand(time(NULL));
        int *A = (int *)malloc(sizeof(int) * B[j]);
        for (int i = 0; i < B[j]; i++)
            A[i] = rand() % 1000;

        heapSort(A, B[j]);
        clock_t end = clock();
        time_spent += (double)(end - begin) / CLOCKS_PER_SEC;
        printf(" The elapsed time is %f seconds\n", time_spent);
    }

    printf("\n\nFor sorted array:\n ");
    for (int j = 0; j < 4; j++)
    {
        printf("For n=%d: ", B[j]);
        clock_t begin = clock();
        int *A = (int *)malloc(sizeof(int) * B[j]);
        A[0] = rand() % 30;
        for (int i = 0; i < B[j]; i++)
            A[i] = A[i - 1] + (rand() % 1000);

        heapSort(A, B[j]);
        clock_t end = clock();
        time_spent += (double)(end - begin) / CLOCKS_PER_SEC;
        printf(" The elapsed time is %f seconds\n", time_spent);
    }

    printf("\n\nFor reverse sorted array:\n ");
    for (int j = 0; j < 4; j++)
    {
        printf("For n=%d: ", B[j]);
        clock_t begin = clock();
        int *A = (int *)malloc(sizeof(int) * B[j]);
        A[B[j] - 1] = rand() % 10;
        for (int i = (B[j] - 2); i >= 0; i--)
        {
            A[i] = A[i + 1] + (rand() % 1000);
        }

        heapSort(A, B[j]);
        clock_t end = clock();
        time_spent += (double)(end - begin) / CLOCKS_PER_SEC;
        printf(" The elapsed time is %f seconds\n", time_spent);
    }
    return 0;
}

Output

For random array:

 For n=20000:  The elapsed time is 0.005000 seconds

For n=50000:  The elapsed time is 0.019000 seconds

For n=100000:  The elapsed time is 0.051000 seconds

For n=500000:  The elapsed time is 0.226000 seconds

For sorted array:

 For n=20000:  The elapsed time is 0.232000 seconds

For n=50000:  The elapsed time is 0.244000 seconds

For n=100000:  The elapsed time is 0.271000 seconds

For n=500000:  The elapsed time is 0.434000 seconds

For reverse sorted array:

 For n=20000:  The elapsed time is 0.438000 seconds

For n=50000:  The elapsed time is 0.451000 seconds

For n=100000:  The elapsed time is 0.474000 seconds

For n=500000:  The elapsed time is 0.605000 seconds