Selection Sort is a simple comparison-based sorting algorithm that divides the array into a sorted and an unsorted part. It repeatedly selects the smallest (or largest) element from the unsorted part and swaps it with the first element of the unsorted portion. While easy to implement, Selection Sort is not efficient for large datasets, with a time complexity of O(n²).
Understanding the Problem
The key idea in Selection Sort is to minimize the number of swaps compared to Bubble Sort. During each iteration, the algorithm finds the minimum element in the unsorted portion and moves it to its correct position. This ensures that after each pass, the sorted portion of the array grows by one element.
Program 1: Iterative Selection Sort
This program demonstrates the iterative implementation of Selection Sort to sort an integer array in ascending order.
#include <stdio.h>
// Function to perform selection sort
void selectionSort(int arr[], int size) {
int i, j, minIndex, temp;
for (i = 0; i < size - 1; i++) {
minIndex = i;
for (j = i + 1; j < size; j++) {
if (arr[j] < arr[minIndex])
minIndex = j; // Find the minimum element
}
// Swap the found minimum element with the first element
temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
}
// Function to display array
void display(int arr[], int size) {
for (int i = 0; i < size; i++)
printf("%d ", arr[i]);
printf("\n");
}
int main() {
int arr[] = {4, 7, 8, 1, 5, 3, 2, 6, 9};
int size = sizeof(arr) / sizeof(arr[0]);
printf("Original array: ");
display(arr, size);
selectionSort(arr, size);
printf("Sorted array: ");
display(arr, size);
return 0;
}In this approach, the outer loop iterates over each position of the array, while the inner loop finds the minimum element in the unsorted portion. Swapping is done only once per pass, reducing unnecessary swaps compared to Bubble Sort.
Program 2: Recursive Selection Sort
This program demonstrates Selection Sort implemented recursively. The recursion reduces the size of the unsorted array in each call.
#include <stdio.h>
// Recursive selection sort function
void selectionSortRecursive(int arr[], int start, int size) {
if (start >= size - 1)
return; // Base case: array is sorted
int minIndex = start;
for (int i = start + 1; i < size; i++) {
if (arr[i] < arr[minIndex])
minIndex = i; // Find minimum element in remaining array
}
// Swap the found minimum element with the first element
int temp = arr[start];
arr[start] = arr[minIndex];
arr[minIndex] = temp;
// Recursive call for the remaining unsorted array
selectionSortRecursive(arr, start + 1, size);
}
// Function to display array
void display(int arr[], int size) {
for (int i = 0; i < size; i++)
printf("%d ", arr[i]);
printf("\n");
}
int main() {
int arr[] = {4, 7, 8, 1, 5, 3, 2, 6, 9};
int size = sizeof(arr) / sizeof(arr[0]);
printf("Original array: ");
display(arr, size);
selectionSortRecursive(arr, 0, size);
printf("Sorted array: ");
display(arr, size);
return 0;
}In the recursive method, each call identifies the minimum element in the remaining unsorted portion and moves it to its correct position. The recursion terminates when the unsorted portion has only one element left.
FAQs
Q1: Is Selection Sort stable?
No, Selection Sort is not stable because swapping may change the relative order of equal elements.
Q2: What is the time complexity?
Both average and worst-case time complexity: O(n²).
Q3: How many swaps does Selection Sort perform?
At most n-1 swaps, which is fewer than Bubble Sort.
Q4: Can Selection Sort be used for descending order?
Yes, simply select the maximum element instead of the minimum in each pass.
Conclusion
Selection Sort is a simple and educational sorting algorithm. While it is inefficient for large datasets, it provides a clear demonstration of sorting logic. Recursive and iterative implementations show flexibility in approach, making it useful for learning algorithm design and recursion fundamentals.
References & Additional Resources
- Kernighan, Brian W., and Dennis M. Ritchie. The C Programming Language. 2nd Edition, Prentice Hall, 1988.
- Data Structures Using C by Reema Thareja – A well-regarded textbook covering core C language constructs and data structures, including sorting algorithms like selection sort.
- Selection Sort – GeeksforGeeks – A clear walkthrough of the selection sort algorithm in C, explaining how each pass selects the smallest remaining element and swaps it into position.
- Selection Sort – Programiz – Step-by-step guide with pseudocode and implementations in various languages, including C, plus a visual breakdown of how minimum elements are found and swapped.
