Write a menu driven program as given below, to sort an array of n integers in ascendingorder by insertion sort algorithm and determine the time required to sort the elements.Repeat the experiment for different values of n and different nature of data (i.e. applyinsertion sort algorithm on the data of array that are already sorted, reversely sorted andrandom data). Finally plot a graph of the time taken versus n for each type of data. Theelements can be read from a file or can be generated using the random number generator.
INSERTION SORT MENU
0. Quit
1. n Random numbers Array
2. Display the Array
3. Sort the Array in Ascending Order by using Insertion Sort Algorithm
4. Sort the Array in Descending Order by using any sorting Algorithm
5. Time Complexity to sort ascending of random data
6. Time Complexity to sort ascending of data already sorted in ascending order
7. Time Complexity to sort ascending of data already sorted in descending order
8. Time Complexity to sort ascending of data for all Cases (Data Ascending, Data in
descending & Random Data) in Tabular form for values n=5000 to 50000, step=5000
Table
Sl No. | Value of n | Time Complexity (Random Data) | Time Complexity (Data in descending) | Time Complexity (Data in Ascending) |
1 | 5000 | 0.020972 | 0.040426 | 0.000022 |
2 | 10000 | 0.089113 | 0.171431 | 0.000048 |
3 | 15000 | 0.203482 | 0.416248 | 0.000064 |
4 | 20000 | 0.352713 | 0.700903 | 0.000136 |
5 | 25000 | 0.714418 | 1.104327 | 0.000106 |
6 | 30000 | 0.820621 | 1.594471 | 0.000127 |
7 | 35000 | 1.073199 | 2.123541 | 0.000151 |
8 | 40000 | 1.371838 | 2.635363 | 0.000169 |
9 | 45000 | 1.846300 | 3.849002 | 0.000190 |
10 | 50000 | 2.488527 | 5.622120 | 0.000213 |
Program
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
int arr[50000];
void insertData(int arr[], int *n)
{
printf("Enter the number of elements of array (max : 50000): ");
scanf("%d", n);
if (*n > 50000)
{
printf("\nCannot be more than 50000\n");
return;
}
srand(time(0));
for (int i = 0; i < *n; i++)
arr[i] = rand() % 1000;
printf("Data insertion completed\n");
}
void display(int arr[], int n)
{
printf("\nElements of the array : \n");
for (int i = 0; i < n; i++)
{
printf("%d ", arr[i]);
}
}
double insertionSort(int arr[], int n)
{
int i, key, j, count = 0;
clock_t start,end;
double total_cputime;
start=clock();
for (i = 1; i < n; i++)
{
key = arr[i];
j = i - 1;
count++;
while (j >= 0 && arr[j] > key)
{
arr[j + 1] = arr[j];
j = j - 1;
count++;
}
arr[j + 1] = key;
}
end=clock();
total_cputime=((double)(end-start))/CLOCKS_PER_SEC;
return total_cputime;
}
double insertionSortDESC(int arr[], int n)
{
int i, key, j, count = 0;
clock_t start,end;
double total_cputime;
start=clock();
for (i = 1; i < n; i++)
{
key = arr[i];
j = i - 1;
count++;
while (j >= 0 && arr[j] < key)
{
arr[j + 1] = arr[j];
j = j - 1;
count++;
}
arr[j + 1] = key;
}
end=clock();
total_cputime=((double)(end-start))/CLOCKS_PER_SEC;
return total_cputime;
}
void displayAll()
{
int size = 0;
srand(time(0));
printf("\n\nN value\t Time(RANDOM DATA))\t Time(ASC DATA)\t Time(DESC DATA)\n");
for (int i = 0; i < 10; i++)
{
size = size + 5000;
for (int j = 0; j < size; j++)
arr[j] = rand() % 50000;
double time_random = insertionSort(arr, size);
double time_asc = insertionSort(arr, size);
double time_desc = insertionSortDESC(arr, size);
time_desc = insertionSort(arr, size);
printf("%d\t\t %lf\t\t %lf\t\t %lf\n", size, time_random, time_asc, time_desc);
}
printf("\n\n");
}
int main()
{
int choice, n, steps;
double iSortSteps;
while (1)
{
printf("\nMENU\n");
printf("\n0. Quit");
printf("\n1. Insert data to array");
printf("\n2. Display");
printf("\n3. Sort array in ascending using insertion");
printf("\n4. Sort array in descending");
printf("\n5. Time complexity to sort in ascending order");
printf("\n6. Time complexity to sort in ascending already in ascending order");
printf("\n7. Time complexity to sort in ascending already in descending order");
printf("\n8. Display Time Complexity to sort in ascending order for all cases");
printf("\n\nEnter your choice : ");
scanf("%d", &choice);
switch (choice)
{
case 0:
printf("\nDankie!\n");
exit(0);
case 1:
insertData(arr, &n);
break;
case 2:
display(arr, n);
break;
case 3:
iSortSteps = insertionSort(arr, n);
printf("Sorting completed successfully [ascending]\n");
break;
case 4:
steps = insertionSortDESC(arr, n);
printf("Sorting completed successfully [descending]\n");
break;
case 5:
printf("The number of steps for ascending sorting using insertion sort : %lf\n", insertionSort(arr, n));
break;
case 6:
iSortSteps = insertionSort(arr, n);
printf("The number of steps for ascending sorting of ascending sorted array : %lf\n", insertionSort(arr, n));
break;
case 7:
iSortSteps = insertionSortDESC(arr, n);
printf("The number of steps for ascending sorting of desscending sorted array : %lf\n", insertionSort(arr, n));
break;
case 8:
displayAll();
break;
default:
break;
}
}
return 0;
}
Output
MENU
0. Quit
1. Insert data to array
2. Display
3. Sort array in ascending using insertion
4. Sort array in descending
5. Time complexity to sort in ascending order
6. Time complexity to sort in ascending already in ascending order
7. Time complexity to sort in ascending already in descending order
8. Display Time Complexity to sort in ascending order for all cases
Enter your choice : 1
Enter the number of elements of array (max : 50000): 10 11 12 13 14 15
Data insertion completed
Enter your choice : 3
Sorting completed successfully [ascending]
MENU
0. Quit
1. Insert data to array
2. Display
3. Sort array in ascending using insertion
4. Sort array in descending
5. Time complexity to sort in ascending order
6. Time complexity to sort in ascending already in ascending order
7. Time complexity to sort in ascending already in descending order
8. Display Time Complexity to sort in ascending order for all cases
Enter your choice : 2
Elements of the array :
61 139 243 450 507 537 592 923 974 995
Enter your choice : 4
Sorting completed successfully [descending]
Enter your choice : 2
Elements of the array :
995 974 923 592 537 507 450 243 139 61
Enter your choice : 5
The number of steps for ascending sorting using insertion sort : 0.000003
Enter your choice : 6
The number of steps for ascending sorting of ascending sorted array : 0.000002
Enter your choice : 7
The number of steps for ascending sorting of desscending sorted array : 0.000002
Graph
