Selection Sort
Selection sort is a simple sorting algorithm that divides the input list into two parts: a sorted sublist of items which is built up from left to right at the front of the list, and a sublist of the remaining unsorted items that occupy the rest of the list. Initially, the sorted sublist is empty, and the unsorted sublist is the entire input list. The algorithm proceeds by finding the smallest (or largest, depending on sorting order) element in the unsorted sublist, exchanging it with the leftmost unsorted element (putting it in sorted order), and moving the sublist boundaries one element to the right.
Let's consider an example with the list [29, 10, 14, 37, 13]
. We'll go through the selection sort process, illustrating each step with ASCII art.
Initial List:
29 10 14 37 13
1st Iteration (Find the minimum element and swap it with the first element):
Minimum:
10
Swap
10
and29
10 29 14 37 13
^^^^^^^^^^^^^^^^
2nd Iteration (Find the minimum element in the remaining list and swap with the 2nd element):
Minimum:
13
Swap
13
and29
10 13 14 37 29
^^^^^^^^^^^
3rd Iteration (Find the minimum in the rest and swap with the 3rd element):
- No swap needed as
14
is already in correct position
10 13 14 37 29
^^^^^^^
4th Iteration (Find the minimum in the last two and swap if needed):
Minimum:
29
Swap
29
and37
10 13 14 29 37
^^^
5th Iteration:
- Not needed as the list is already sorted
The final sorted list is [10, 13, 14, 29, 37]
.
In each iteration, the range of the unsorted list (denoted by ^
) gets smaller as the smallest elements get sorted to the front. This process continues until the entire list is sorted.
Here is the pseudo code for the Selection Sort algorithm:
SelectionSort(A: array of values)
n = length(A)
for i = 0 to n-1
// Set current element as minimum
min_index = i
// Check the rest of the array to find the minimum
for j = i+1 to n-1
if A[j] < A[min_index]
min_index = j
// Swap the found minimum element with the current element
if min_index != i
swap A[i] and A[min_index]
This pseudo-code outlines the basic process of the Selection Sort:
Iterate over the array, treating each element as the current minimum.
For each position
i
in the array, find the smallest element in the rest of the array (fromi+1
ton-1
).If the found minimum is not the element at position
i
(i.e., there's a smaller element found in the rest of the array), swap the elements.Repeat this process until the entire array is sorted.
Here's the C code for the Selection Sort algorithm:
#include <stdio.h>
void selectionSort(int arr[], int n) {
int i, j, min_index, temp;
// One by one move boundary of unsorted subarray
for (i = 0; i < n-1; i++) {
// Find the minimum element in unsorted array
min_index = i;
for (j = i+1; j < n; j++) {
if (arr[j] < arr[min_index]) {
min_index = j;
}
}
// Swap the found minimum element with the first element
temp = arr[min_index];
arr[min_index] = arr[i];
arr[i] = temp;
}
}
// Function to print an array
void printArray(int arr[], int size) {
int i;
for (i=0; i < size; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}
// Driver program to test above functions
int main() {
int arr[] = {64, 25, 12, 22, 11};
int n = sizeof(arr)/sizeof(arr[0]);
selectionSort(arr, n);
printf("Sorted array: \n");
printArray(arr, n);
return 0;
}
Explanation of the code:
Function Declaration: The function
selectionSort
is declared which takes an arrayarr[]
and its sizen
as arguments.Outer Loop: The first
for
loop runs from the start of the array to the second-to-last element. It represents the current position in the array where we're placing the smallest unsorted element.Finding Minimum Element: Inside this loop, we initialize
min_index
to the current positioni
. Then, another nestedfor
loop starts from the next element to the end of the array. This inner loop is used to find the index of the minimum element in the unsorted part of the array.Swapping Elements: After finding the minimum element in the unsorted part, we swap it with the element at the current position
i
. We use a temporary variabletemp
for this purpose.Printing the Array: The
printArray
function is a utility to print the elements of an array.Driver Code: In
main
, we declare an arrayarr[]
and determine its size. We then callselectionSort
with this array, and finally, print the sorted array.
This C code effectively sorts an array using the Selection Sort algorithm, which is an in-place comparison sort. The algorithm is not suitable for large datasets as its average and worst-case complexity are of O(n^2)
, where n
is the number of items.
The complexity analysis of the Selection Sort algorithm involves evaluating both its time complexity and space complexity.
Time Complexity
Best, Average, and Worst Cases:
Best Case: Even in the best case, where the array is already sorted, the algorithm still goes through the entire array to check if the element is the minimum in the remaining part of the array. So, the best-case complexity is O(n^2).
Average Case: On average, the algorithm performs the same number of comparisons, which is O(n^2).
Worst Case: The worst-case scenario is also O(n^2), which happens when the array is in reverse order.
The key operation in the time complexity analysis is the number of comparisons. For each element in the array, the algorithm searches the rest of the array to find the minimum element. If the array has n
elements, the first element is compared with n-1
elements, the second with n-2
, and so on, leading to n(n-1)/2
comparisons, which simplifies to O(n^2).
Nested Loops:
- The outer loop runs
n-1
times, and for each iteration of the outer loop, the inner loop runsn-i
times (wherei
is the current iteration of the outer loop). This nested loop structure contributes to the quadratic time complexity.
- The outer loop runs
Space Complexity
- Space Complexity: The space complexity of Selection Sort is O(1), which means it is a constant space, in-place sorting algorithm. Regardless of the size of the input, the algorithm requires the same amount of additional space (for variables like
i
,j
,min_index
, andtemp
). This makes it an in-place sorting algorithm.
Important to note
Selection Sort is not a scalable sorting algorithm for large datasets due to its quadratic time complexity (O(n^2)).
It is, however, an in-place sort with minimal additional memory usage, making its space complexity desirable at O(1).
Its performance is not affected by the initial arrangement of elements in the array, as it always performs O(n^2) comparisons.