Sorting Algorithms
Selection Sort

Selection Sort

Time Complexity

BestAverageWorst
Ω(n^2)Θ(n^2)O(n^2)

Space Complexity

Worst
O(1)

Overview

Selection sort is a simple (also comparison-based) sorting algorithm. It works by repeatedly finding the minimum element from the unsorted part of the array and swapping it with the first element of the unsorted part. This process is repeated until the entire array is sorted.

Off with the theoretical definition, here are the exact steps of the algorithm:

  1. Start with the first element of the array as the "sorted part."
  2. Find the minimum element in the remaining unsorted part of the array.
  3. If smaller, swap the minimum element with the first element of the unsorted part.
  4. Expand the "sorted part" by one element, and repeat steps 2 and 3 until the entire array is sorted.

So let's apply the selection sort algorithm to the input array from the animation above: [5, 3, 4, 6, 1, 2]:

  • Initial Array: [5, 3, 4, 6, 1, 2]
    • The first element, 5, is considered the "sorted part.". We don't touch it initially.
  • Find the minimum element in the unsorted part (3, 4, 6, 1, 2), which is 1.
    • Swap 5 and 1: [1, 3, 4, 6, 5, 2]
  • Expand the "sorted part" to include the first two elements (1, 3).
  • Find the minimum element in the unsorted part (4, 6, 5, 2), which is 2.
    • Swap 3 and 2: [1, 2, 4, 6, 5, 3]
  • Expand the "sorted part" to include the first three elements (1, 2, 4).
  • Find the minimum element in the unsorted part (6, 5, 3), which is 3.
    • Swap 4 and 3: [1, 2, 3, 6, 5, 4]
  • Expand the "sorted part" to include the first four elements (1, 2, 3, 6).
  • Find the minimum element in the unsorted part (5, 4), which is 4.
    • Swap 6 and 4: [1, 2, 3, 4, 5, 6]
  • Expand the "sorted part" to include the first five elements (1, 2, 3, 4, 5).
  • Find the minimum element in the unsorted part (6), which is 5.
    • Swap 5 and 5 (no change): [1, 2, 3, 4, 5, 6]

The entire array is now sorted - [1, 2, 3, 4, 5, 6]

Easy, isn't it?

Now back to some theory!

The selection sort algorithm has a time complexity of O(n^2) - it involves two nested loops to find the minimum element and place it in its correct position. Even considering its simplicity, it is not the most efficient sorting algorithm for large arrays, but it can be useful for small arrays or as a step in more complex sorting algorithms. Also, it's a great algorithm for learning purposes and getting into algorithms, and for exams too!

Code



def selection_sort(arr):
    n = len(arr)
    for i in range(n):
        min_index = i
        for j in range(i + 1, n):
            if arr[j] < arr[min_index]:
                min_index = j
        arr[i], arr[min_index] = arr[min_index], arr[i]
 
arr = [5, 3, 4, 6, 1, 2]
selection_sort(arr)
print(arr)  # Output: [1, 2, 3, 4, 5, 6]
 
function selectionSort(arr) {
    const n = arr.length;
    for (let i = 0; i < n; i++) {
        let minIndex = i;
        for (let j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
    }
}
 
let arr = [5, 3, 4, 6, 1, 2];
selectionSort(arr);
console.log(arr); // Output: [1, 2, 3, 4, 5, 6]
 
 
public class SelectionSort {
    public static void selectionSort(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n; i++) {
            int minIndex = i;
            for (int j = i + 1; j < n; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }
            int temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        }
    }
 
    public static void main(String[] args) {
        int[] arr = {5, 3, 4, 6, 1, 2};
        selectionSort(arr);
        for (int num : arr) {
            System.out.print(num + " "); // Output: 1 2 3 4 5 6
        }
    }
}
 
 
#include <stdio.h>
 
void selectionSort(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        int minIndex = i;
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        int temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
    }
}
 
int main() {
    int arr[] = {5, 3, 4, 6, 1, 2};
    int n = sizeof(arr) / sizeof(arr[0]);
    selectionSort(arr, n);
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]); // Output: 1 2 3 4 5 6
    }
    return 0;
}
 
 
function selectionSort(&$arr) {
    $n = count($arr);
    for ($i = 0; $i < $n; $i++) {
        $minIndex = $i;
        for ($j = $i + 1; $j < $n; $j++) {
            if ($arr[$j] < $arr[$minIndex]) {
                $minIndex = $j;
            }
        }
        list($arr[$i], $arr[$minIndex]) = array($arr[$minIndex], $arr[$i]);
    }
}
 
$arr = [5, 3, 4, 6, 1, 2];
selectionSort($arr);
print_r($arr); // Output: Array ( [0] => 1 [1] => 2 [2] => 3 [3] => 4 [4] => 5 [5] => 6 )
We always try to improve this course so if you spot errors, inconsistencies or other issues, contact us.
Insertion SortBubble Sort