The Selection Sort Algorithm sorts the elements of an array. In this article, we shall look at the core algorithm and how we can implement it in Python, Java, C++, and C.
The Core Algorithm
The Selection Sort Algorithm is very simple.
- Set i = 0 initially, since that is the starting point.
- Find the minimum element of the unsorted sub-array [i..end]
- We then swap this with the element at the position a[i].
- We then increment i, and repeat the above steps until i == n
In pseudo-code, we can represent it like this:
PROCEDURE SELECTION_SORT(arr):
i = -1
while i < size(arr):
idx = find_min(arr[i+1..size(arr)])
swap(i, idx)
i++
return arr
Showing the working of the Algorithm
Let’s now understand how this algorithm works, by applying it on an array!
Let’s consider the below array.
Initially, the unsorted array looks like this:
In the first iteration, we find the minimum element from the remaining array (from {12, 7, 6, 16, 4}), which is 4. We now swap arr[i] with 4.
In the next iteration, we find the minimum element from the subarray {7, 6, 16, 12}, which is 6. So let’s swap 6 and 7.
Now, we move to the next element of the updated array and again do the same steps.
In the previous iteration, there was no change, since 7 is the minimum element in the remaining sub-array.
Now finally, we reach the end of the array, and now the complete array is sorted!
Let’s apply the Selection Sort Algorithm to sort the above array in Python, C++, and C.
Selection Sort in Python
The below snippet shows the working of the algorithm using Python.
def find_min(arr, start, end):
minimum = arr[start]
min_idx = start
for idx in range(start, end):
if arr[idx] < minimum:
minimum = arr[idx]
min_idx = idx
return min_idx
def selection_sort(arr):
i = 0
arr_size = len(arr)
while i < arr_size:
# Find minimum of remaining unsorted subarray
min_idx = find_min(arr, i, arr_size)
# Swap with arr[i]
arr[min_idx], arr[i] = arr[i], arr[min_idx]
i += 1
return arr
a = [12, 7, 6, 16, 4]
print(selection_sort(a))
Output
[4, 6, 7, 12, 16]
Selection Sort in Java
public class SelectionSort {
int find_min(int arr[], int start, int end) {
int min_idx = start;
int minimum = arr[start];
for (int i=start; i<end; i++) {
if (arr[i] < minimum) {
min_idx = i;
minimum = arr[i];
}
}
return min_idx;
}
void selection_sort(int arr[], int arr_len) {
// Selection Sort on an Array
// Pass by reference
int start = 0;
int min_idx;
while (start < arr_len) {
min_idx = find_min(arr, start, arr_len);
// Swap arr[start] and arr[min_idx]
int temp = arr[start];
arr[start] = arr[min_idx];
arr[min_idx] = temp;
start++;
}
}
public static void main(String[] args) {
int arr[] = {12, 7, 6, 16, 4};
SelectionSort sel_sort = new SelectionSort();
sel_sort.selection_sort(arr, 5);
System.out.println("Array after sorting:");
for (int i=0; i<5; i++) {
System.out.printf("%d ", arr[i]);
}
System.out.println();
}
}
Save the above code as SelectionSort.java.
Output
Array after sorting:
4 6 7 12 16
Selection Sort in C++
Here is another implementation of the algorithm in C++
#include <iostream>
using namespace std;
int find_min(int arr[], int start, int end) {
int min_idx = start;
int minimum = arr[start];
for (int i=start; i<end; i++) {
if (arr[i] < minimum) {
min_idx = i;
minimum = arr[i];
}
}
return min_idx;
}
void selection_sort(int arr[], int arr_len) {
// Selection Sort on an Array
// Pass by reference
int start = 0;
int min_idx;
while (start < arr_len) {
min_idx = find_min(arr, start, arr_len);
// Swap arr[start] and arr[min_idx]
int temp = arr[start];
arr[start] = arr[min_idx];
arr[min_idx] = temp;
start++;
}
}
int main() {
int arr[] = {12, 7, 6, 16, 4};
selection_sort(arr, 5);
cout << "Array after sorting:\n";
for (int i=0; i<5; i++) {
cout << arr[i] << " ";
}
cout << endl;
return 0;
}
Output
Array after sorting:
4 6 7 12 16
Selection Sort in C
#include <stdio.h>
int find_min(int arr[], int start, int end) {
int min_idx = start;
int minimum = arr[start];
for (int i=start; i<end; i++) {
if (arr[i] < minimum) {
min_idx = i;
minimum = arr[i];
}
}
return min_idx;
}
void selection_sort(int arr[], int arr_len) {
// Selection Sort on an Array
int start = 0;
int min_idx;
while (start < arr_len) {
min_idx = find_min(arr, start, arr_len);
// Swap arr[start] and arr[min_idx]
int temp = arr[start];
arr[start] = arr[min_idx];
arr[min_idx] = temp;
start++;
}
}
int main() {
int arr[] = {12, 7, 6, 16, 4};
selection_sort(arr, 5);
printf("Array after sorting:\n");
for (int i=0; i<5; i++) {
printf("%d ", arr[i]);
}
printf("\n");
return 0;
}
Output
Array after sorting:
4 6 7 12 16
Time Complexity
Since the algorithm performs 2 loops iterating over the array, it has a time complexity of O(n^2).
If that’s not clear, the total number of operations performed, if the array has n elements is:
(n + (n-1) + (n-2) + (n-3) + … + 1) = n * (n + 1)/2 = O(n^2)
So, while this is not a very good sorting algorithm, it is very easy to implement, and can be used to sort arrays with low number of elements.
Must Reads
References
- Wikipedia Article on Selection Sort