Selection Sort Algorithm

6 August 2023

In this article we are going to discuss the Selection Sort Algorithm. The working procedure of the selection sort algorithm is very simple, like the bubble sort algorithm. Basically, It is a type of algorithm that selects the smallest element from an unsorted list in each iteration and places that element at the beginning of the unsorted list.

It is a simple comparison-based sorting algorithm that divides the input list into two parts:

• Sorted Part
• Unsorted Part

It repeatedly selects the minimum (or maximum, depending on the desired sorting order) element from the unsorted part and swaps it with the first unsorted element until the entire list becomes sorted.

How Selection Sort Algorithms Works?

Let us consider an array as an example –  [8, 0, 7, 1, 13]. Now we have to sort this array using the selection sort algorithm.

First Pass

In the First Pass, we have to find a minimum between 8 and 0. On comparing this, we got 0 as the minimum, then we compared 0 by 7,1,13 and found that 0 was the minimum in all. So we change the index from 0 to i=1 and the 8 is placed in the position of zero. Now, the sorted array is – 0, 8, 7, 1, 13. As you can see, this whole process in the image below.

Second Pass

• Array: `[0, 8, 7, 1, 13]`
• Find the minimum element in the unsorted part `[8, 7, 1, 13]`, which is `1`.
• Swap `8` with `1`: `[0, 1, 7, 8, 13]`

Third Pass

• Array: `[0, 1, 7, 8, 13]`
• Find the minimum element in the unsorted part `[7, 8, 13]`, which is `7`.
• Swap `7` with `7` (no change): `[0, 1, 7, 8, 13]`

Fourth Pass

• Array: `[0, 1, 7, 8, 13]`
• Find the minimum element in the unsorted part `[8, 13]`, which is `8`.
• Swap `8` with `8` (no change): `[0, 1, 7, 8, 13]`

Fifth Pass

• Array: `[0, 1, 7, 8, 13]`
• Find the minimum element in the unsorted part `[13]`, which is `13`.
• Swap `13` with `13` (no change): `[0, 1, 7, 8, 13]`

Now, the array `[0, 1, 7, 8, 13]` is sorted in ascending order using the selection sort algorithm.

Selection Sort Algorithm

Here’s the step-by-step guide :

1. Start with the first element of the array as the starting index for the unsorted part.
2. Repeat the following steps until the entire array is sorted:

a. Assume the current element at the starting index is the minimum (or maximum).

b. Iterate through the remaining unsorted part of the array to find the actual minimum (or maximum) element.

c. Swap the current element with the minimum (or maximum) element found in the previous step.

d. Move the starting index of the unsorted part one step to the right.

Here are the Pseudocode :

```function selection_sort(arr):
n = length of arr

for i from 0 to n-2:
# Assume the current element is the minimum (or maximum)
min_index = i

# Find the actual minimum (or maximum) in the unsorted part
for j from i+1 to n-1:
if arr[j] < arr[min_index]: # For descending order, use '>'
min_index = j

# Swap the current element with the minimum (or maximum) element
swap(arr[i], arr[min_index])

# The array is now sorted in ascending (or descending) order```

Python Program Using Selection Sort Algorithm

Let us take an example of a python program to sort an array using the bubble sort algorithm –

```def selection_sort(arr):
n = len(arr)
for i in range(n - 1):
# Find the minimum element in the remaining unsorted part
min_index = i
for j in range(i + 1, n):
if arr[j] < arr[min_index]:
min_index = j

# Swap the minimum element with the first element in the unsorted part
arr[i], arr[min_index] = arr[min_index], arr[i]

# Example usage:
arr = [8, 0, 7, 1, 13]
print("Original array:", arr)
selection_sort(arr)
print("Sorted array:", arr)```

Output

```Original array: [8, 0, 7, 1, 13]
Sorted array: [0, 1, 7, 8, 13]```

JavaScript Program Using Selection Sort Algorithm

```function selectionSort(arr) {
const n = arr.length;
for (let i = 0; i < n - 1; i++) {
// Assume the current element is the minimum
let minIndex = i;
// Find the actual minimum element in the unsorted part
for (let j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex]) { // For descending order, use '>'
minIndex = j;
}
}
// Swap the current element with the minimum element
[arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
}
// The array is now sorted in ascending order
return arr;
}
// Example usage:
const arr = [8, 0, 7, 1, 13];
console.log("Original array:", arr);
const sortedArray = selectionSort(arr);
console.log("Sorted array:", sortedArray);```

Output

```Original array: [8, 0, 7, 1, 13]
Sorted array: [0, 1, 7, 8, 13]```

C Program Using Selection Sort Algorithm

```#include <stdio.h>
void selectionSort(int arr[], int n) {
for (int i = 0; i < n - 1; i++) {
// Assume the current element is the minimum
int minIndex = i;
// Find the actual minimum element in the unsorted part
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex]) { // For descending order, use '>'
minIndex = j;
}
}
// Swap the current element with the minimum element
int temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
}
// Function to print an array
void printArray(int arr[], int n) {
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}
int main() {
int arr[] = {8, 0, 7, 1, 13};
int n = sizeof(arr) / sizeof(arr[0]);
printf("Original array: ");
printArray(arr, n);
selectionSort(arr, n);
printf("Sorted array: ");
printArray(arr, n);
return 0;
}```

Output

```Original array: 8 0 7 1 13
Sorted array: 0 1 7 8 13```

Java Program Using Selection Sort

```import java.util.Arrays;
public class SelectionSort {
public static void selectionSort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
// Assume the current element is the minimum
int minIndex = i;
// Find the actual minimum element in the unsorted part
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex]) { // For descending order, use '>'
minIndex = j;
}
}
// Swap the current element with the minimum element
int temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
}
public static void main(String[] args) {
int[] arr = {8, 0, 7, 1, 13};
System.out.println("Original array: " + Arrays.toString(arr));
selectionSort(arr);
System.out.println("Sorted array: " + Arrays.toString(arr));
}
}```

Output

```Original array: [8, 0, 7, 1, 13]
Sorted array: [0, 1, 7, 8, 13]```

In the `main` method, we create an array, call the `selectionSort` method to sort it, and then print the original and sorted arrays using `Arrays.toString()` to display the elements.