DAA- C program for Selection Sort to Compare Time Complexity Solved Question

 Write a C program for selection sort to  

I. Compare the time complexity with the given data set given below and calculate the time complexity based on the CPU clock.

II. Plot a graph showing the comparison (n, the input data Vs. CPU times)

Table Data

Sl No.	Value of n	Selection Sort                                                      (Time Complexity)
		Best case	Average case	Worst case
1	5000	0.042095	0.040207	0.045389
2	10000	0.163906	0.153777	0.155101
3	15000	0.293064	0.291044	0.374457
4	20000	0.520930	0.523444	0.760394
5	25000	0.833947	0.812482	1.351761
6	30000	1.177193	1.200825	1.917192
7	35000	1.737118	1.729328	2.741452
8	40000	2.131859	2.164163	3.878107
9	45000	2.673547	2.956670	5.009833
10	50000	3.284646	3.236158	6.463267

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 selectionSort(int array[], int n)
{
    clock_t start,end;
    int c, d, position,t;
    double total_cputime;
    start=clock();
    for (c = 0; c < (n - 1); c++)
    {
        position = c;
        for (d = c + 1; d < n; d++)
        {
            if (array[position] > array[d])
                position = d;
        }
        if (position != c)
        {
            t = array[c];
            array[c] = array[position];
            array[position] = t;
        }
    }
    end=clock();
    total_cputime=((double)(end-start))/CLOCKS_PER_SEC;
    return total_cputime;
}
double selectionSortDESC(int array[], int n)
{
    clock_t start,end;
    int c, d, position,t;
    double total_cputime;
    start=clock();
    for (c = 0; c < (n - 1); c++)
    {
        position = c;

        for (d = c + 1; d < n; d++)
        {
            if (array[position] < array[d])
            position = d;
        }
        if (position != c)
        {
            t = array[c];
            array[c] = array[position];
            array[position] = t;
        }
    }
    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 = selectionSort(arr, size);
        double time_asc = selectionSort(arr, size);
        double time_desc = selectionSortDESC(arr, size);
        time_desc = selectionSort(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 bSortSteps;

    while (1)
    {
        printf("\nMENU\n");
        printf("\n0. Quit");
        printf("\n1. Insert data to array");
        printf("\n2. Display");
        printf("\n3. Sort array in ascending  using selection sort.");
        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("\nGracias!\n");
            exit(0);
        case 1:
            insertData(arr, &n);
            break;
        case 2:
            display(arr, n);
            break;
        case 3:
            bSortSteps = selectionSort(arr, n);
            printf("Sorting completed successfully [ascending]\n");
            break;
        case 4:
            steps = selectionSortDESC(arr, n);
            printf("Sorting completed successfully [descending]\n");
            break;
        case 5:
            printf("Time for ascending sorting using selection sort : %lf\n", selectionSort(arr, n));
            break;
        case 6:
            bSortSteps = selectionSort(arr, n);
            printf("Time for ascending sorting of ascending sorted array : %lf\n", selectionSort(arr, n));
            break;
        case 7:
            bSortSteps = selectionSortDESC(arr, n);
            printf("Time for ascending sorting of desscending sorted array : %lf\n", selectionSort(arr, n));
            break;
        case 8:
            displayAll();
            break;
        default:
            break;
        }
    }

    return 0;
}

Graph