Scribd
Upload
52 views2 pages

Selection Sort Time Complexity Analysis

The document describes a C/C++ program that implements the Selection Sort algorithm to sort a set of integers and measures its time complexity. The program generates random integers, sorts them, and records the time taken for sorting for various input sizes greater than 5000. It also includes functionality to plot the time taken versus the number of elements using gnuplot.

Uploaded by

stephenjoshua4321
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
52 views2 pages

Selection Sort Time Complexity Analysis

The document describes a C/C++ program that implements the Selection Sort algorithm to sort a set of integers and measures its time complexity. The program generates random integers, sorts them, and records the time taken for sorting for various input sizes greater than 5000. It also includes functionality to plot the time taken versus the number of elements using gnuplot.

Uploaded by

stephenjoshua4321
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd

/*

Design and implement C/C++ Program to sort a given set of n integer


elements using Selection Sort method and compute its time complexity. Run
the program for varied values of n> 5000 and record the time taken to
sort. Plot a graph of the time taken versus n. The elements can be read
from a file or can be generated using the random number generator.
*/

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
struct timetaken{
int no_of_elem;
float timetaken;
}t[100];

void selectionSort(int arr[], int n){


int i, j, min_idx;
for (i = 0; i < n-1; i++){
min_idx = i;
for (j = i+1; j < n; j++){
if (arr[j] < arr[min_idx]){
min_idx = j;
}
}
int temp = arr[min_idx];
arr[min_idx] = arr[i];
arr[i] = temp;
}
}

void generateRandomNumbers(int arr[], int n){


for (int i = 0; i < n; i++){
arr[i] = rand() % 1000000;
}
}

void plot_graph(int run_count){


int i;
FILE *fp = fopen("[Link]", "w"); // Open file to store data
for(i=0;i<run_count;i++){
fprintf(fp,"%d %f\n",t[i].no_of_elem,t[i].timetaken);
}
fclose(fp);

FILE *gp = fopen("[Link]", "w");


fprintf(gp, "set xlabel 'Number of Elements'\n");
fprintf(gp, "set ylabel 'Time taken for sorting in ms.'\n");
fprintf(gp, "set title 'Selection Sort Time Complexity'\n");
fprintf(gp, "plot '[Link]' with lines\n");
fclose(gp);
system("gnuplot -p [Link]");
}

int main()
{
int i,n,times=0,count=0;
printf("How many times would you like to run the sorting?");
scanf("%d",&times);
while(count<times){
printf("Enter number of elements: ");
scanf("%d", &n); // Read the number of elements from the user
if (n <= 5000){
printf("Please enter a value greater than 5000\n");
return 1;
}
int *arr = (int *)malloc(n * sizeof(int));
if (arr == NULL){
printf("Memory allocation failed\n");
return 1;
}
generateRandomNumbers(arr, n);
// printf("Before Sorting:");
// for(i=0 ; i<n; i++)
// printf("%d\t",arr[i]);
clock_t start = clock();
selectionSort(arr, n);
clock_t end = clock();
double time_taken = (((double)(end - start)) /
CLOCKS_PER_SEC)*1000;
// printf("\n\nAfter Sorting:");
// for(i=0 ; i<n; i++)
// printf("%d\t",arr[i]);
printf("Time taken to sort %d elements: %0.2f seconds\n",
n,time_taken);
free(arr);
t[count].no_of_elem=n;
t[count].timetaken=time_taken;
count++;
}
plot_graph(times);
return 0;
}

You might also like