[go: up one dir, main page]
Scribd
Upload
47 views2 pages

Selection Sort Time Complexity Analysis

The document outlines a lab assignment for the Analysis & Design of Algorithms course, requiring students to implement a C program that sorts integers using the Selection Sort method and measures its time complexity for values of n greater than 5000. Students are instructed to generate random integers and record the sorting time for varying sizes of n, ultimately plotting the results. Sample output data is provided, showing the time taken to sort arrays of increasing sizes.

Uploaded by

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

Selection Sort Time Complexity Analysis

The document outlines a lab assignment for the Analysis & Design of Algorithms course, requiring students to implement a C program that sorts integers using the Selection Sort method and measures its time complexity for values of n greater than 5000. Students are instructed to generate random integers and record the sorting time for varying sizes of n, ultimately plotting the results. Sample output data is provided, showing the time taken to sort arrays of increasing sizes.

Uploaded by

khairunnisakmahmed
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 2

Analysis & Design of Algorithms Lab-BCSL404 IV Semester

Design and implement C Program to sort a given set of n integer elements using SelectionSort
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>

// Function to perform selection sort


void selectionSort(int arr[], int n) {
for (int i = 0; i < n - 1; ++i) {
int minIndex = i;
for (int j = i + 1; j < n; ++j) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
// Swap the found minimum element with the first element
int temp = arr[minIndex];
arr[minIndex] = arr[i];
arr[i] = temp;
}
}

int main() {
srand(time(NULL)); // Seed for random number generation

const int numPoints = 10; // Number of data points


const int startingN = 5000; // Starting value of n
const int stepSize = 5000; // Step size for increasing n
printf("n\tTime (seconds)\n");

// Loop through different values of n and record time taken


for (int i = 0; i < numPoints; ++i) {
int n = startingN + i * stepSize;
int* arr = (int*)malloc(n * sizeof(int));

// Generate random numbers


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

// Measure time taken for sorting


clock_t start = clock();

Dept.of CSE, SECAB. I. E. T., Vijayapur 1


Analysis & Design of Algorithms Lab-BCSL404 IV Semester

selectionSort(arr, n);
clock_t end = clock();

double timeTaken = ((double)(end - start)) / CLOCKS_PER_SEC;


printf("%d\t%f\n", n, timeTaken);

free(arr); // Free memory allocated for array


}

return 0;
}

OUTPUT

n Time (seconds)
5000 0.036999
10000 0.145735
15000 0.302012
20000 0.497512
25000 0.779823
30000 1.125217
35000 1.557287
40000 2.031235
45000 2.517561
50000 3.112581

Plot the graph from the above values

Dept.of CSE, SECAB. I. E. T., Vijayapur 2

You might also like