Selection Sort
Selection Sort repeatedly finds the minimum element from the unsorted portion of an array and places it at the correct position. This implementation measures time complexity empirically.
Introduction
Selection Sort is a simple in-place comparison sorting algorithm. It divides the array into a sorted and unsorted region. At each step, it finds the minimum element from the unsorted region and swaps it into its correct position. This VTU lab program also measures actual execution time for different input sizes to demonstrate O(n²) behavior empirically.
Problem Statement
Sort an array of n elements using Selection Sort and analyze its time complexity by measuring execution time for arrays of sizes 5000, 10000, 15000, and 20000.
Real World Applications
- → Small datasets where code simplicity matters
- → Embedded systems with limited memory
- → Educational purposes for understanding sorting
- → When the number of swaps must be minimized
- → Checking if an array is nearly sorted
Algorithm Explanation
For each position i from 0 to n-2, find the index of the minimum element in the subarray a[i..n-1]. Swap a[i] with a[minIndex]. After n-1 passes, the array is sorted. The number of comparisons is always n(n-1)/2 regardless of input order, making it O(n²) in all cases.
Step-by-Step Procedure
- 1 For i = 0 to n-2:
- 2 Set minIndex = i.
- 3 For j = i+1 to n-1: if a[j] < a[minIndex], set minIndex = j.
- 4 Swap a[i] with a[minIndex].
- 5 Array is now sorted.
- 6 For time analysis: generate random arrays of sizes 5000, 10000, 15000, 20000.
- 7 Measure and print execution time for each size.
Complete C Program
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
void selection(int arr[], int n) {
int temp, i, j;
for(i = 0; i < n - 1; i++) {
int minIndex = i;
for(j = i + 1; j < n; j++) {
if(arr[j] < arr[minIndex])
minIndex = j;
}
temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
}
void generateRandomArray(int arr[], int n) {
srand(time(NULL));
for(int i = 0; i < n; i++)
arr[i] = rand();
}
int main() {
int num_values[] = {5000, 10000, 15000, 20000};
int n_values = 4;
for(int i = 0; i < n_values; i++) {
int n = num_values[i];
int *arr = (int *)malloc(n * sizeof(int));
generateRandomArray(arr, n);
clock_t start = clock();
selection(arr, n);
clock_t end = clock();
double time_taken = (double)(end - start) / CLOCKS_PER_SEC;
printf("%d\t%f\n", n, time_taken);
free(arr);
}
return 0;
}Sample Input & Output
(No input required — generates random arrays)n Time_taken
5000 0.023401
10000 0.091200
15000 0.205300
20000 0.364700Dry Run / Trace
For array [64, 25, 12, 22, 11]: Pass 1: min=11 at index 4. Swap a[0] and a[4] → [11, 25, 12, 22, 64] Pass 2: min=12 at index 2. Swap a[1] and a[2] → [11, 12, 25, 22, 64] Pass 3: min=22 at index 3. Swap a[2] and a[3] → [11, 12, 22, 25, 64] Pass 4: min=25 at index 3. Already in place → [11, 12, 22, 25, 64] Sorted!
Advantages & Disadvantages
✓ Advantages
- + Simple to understand and implement
- + In-place sorting — O(1) extra space
- + Minimizes number of swaps (n-1 swaps maximum)
- + Performance is not affected by initial order
✗ Disadvantages
- − O(n²) in all cases — slow for large datasets
- − Not stable (does not preserve relative order of equal elements)
- − Much slower than O(n log n) algorithms for large n
Viva Questions & Answers
Q1. What is the time complexity of Selection Sort in all cases?
O(n²) in best, average, and worst case, because it always makes n(n-1)/2 comparisons regardless of the input.
Q2. Is Selection Sort stable?
No, Selection Sort is not stable. The swap operation can change the relative order of equal elements.
Q3. How many swaps does Selection Sort perform?
At most n-1 swaps (one per pass), making it ideal when swap operations are expensive.
Q4. When is Selection Sort preferred?
When memory writes are costly, since it minimizes swaps. Also for small datasets due to its simplicity.
Q5. What is the difference between Selection Sort and Bubble Sort?
Selection Sort finds the minimum and places it correctly in each pass (at most 1 swap/pass). Bubble Sort repeatedly swaps adjacent elements (many swaps/pass).