Compare running time (in seconds) of heap sort with insertion sort, merge sort, and quick sort on different input sizes and also for different input types (random/sorted/reverse-sorted).
Code #include <stdio.h>
#include <stdlib.h>
#include <time.h>
int Reversesorted(int arr[], int start, int end) //To reverse the array
{
while (start <= end)
{
int temp;
temp = arr[start];
arr[start] = arr[end];
arr[end] = temp;
start++;
end--;
}
}
void heapify(int arr[], int n, int i) //To maintain that the paraent is always greater then its children
{
int largest = i;
int l = 2 * i + 1;
int r = 2 * i + 2;
if (l < n && arr[l] > arr[largest])
largest = l;
if (r < n && arr[r] > arr[largest])
largest = r;
if (largest != i)
{
int temp = arr[i];
arr[i] = arr[largest];
arr[largest] = temp;
heapify(arr, n, largest);
}
}
void heapSort(int arr[], int n) //To maintain the heap
{
int i;
for (i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);
for (i = n - 1; i > 0; i--)
{
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
heapify(arr, i, 0);
}
}
int main()
{
int size[4];
size[0] = 20000;
size[1] = 50000;
size[2] = 100000;
size[3] = 500000;
int j;
printf("\t\tFor the random\t\tFor the Sort Array\t\tFor the Reverse sorted Array");
for (j = 0; j < 4; j++)
{
int *arr;
int i;
clock_t start, end;
arr = (int *)malloc(size[j] * sizeof(int)); //Creating the array dynamically
for (i = 0; i < size[j]; i++) //Putting the value in array in random value
{
arr[i] = rand() % 1000;
}
start = clock(); //Starting time of heap sort
heapSort(arr, size[j]); //Calling the function for sorting the number
end = clock();
//Ending time of the heap sort
double time;
time = ((double)(end - start)) / CLOCKS_PER_SEC; //Time requried to sort the array
printf("\nFor n=%d\t%f sec", size[j], time); //printing the time requried to sort the array
//for sorted array
start = clock(); //Starting time of heap sort
heapSort(arr, size[j]); //Calling the function for sorting the number
end = clock(); //Ending time of the heap sort
time = ((double)(end - start)) / CLOCKS_PER_SEC; //Time requried to sort the array
printf("\t\t%f sec", time);
//printing the time requried to sort the array
//for reverse sorted
Reversesorted(arr, 0, (size[j] - 1));
start = clock(); //Starting time of heap sort
heapSort(arr, size[j]); //Calling the function for sorting the number
end = clock(); //Ending time of the heap sort
time = ((double)(end - start)) / CLOCKS_PER_SEC; //Time requried to sort the array
printf("\t\t\t%f sec", time);
//printing the time requried to sort thearray
free(arr); //Removing the dynamically created array
}
}
Output random Array Sort Array Reverse sorted Array
For n=20000 0.005614 sec 0.004757 sec 0.004450 sec
For n=50000 0.014708 sec 0.011120 sec 0.011857 sec
For n=100000 0.032067 sec 0.024582 sec 0.026023 sec
For n=500000 0.188693 sec 0.129355 sec 0.112625 sec
Tags:
DAA