Offensive Security Researcher & Quantum Cryptography Analyst

Selection Sort Algorithm: Working, Explanation, and Simple Sorting Technique

Abdul Wahab Junaid
selection sort algorithm and working of this algorithm

I like to describe selection sort as the most intuitive sorting algorithm I know, because it mirrors exactly how a person might sort a hand of playing cards by repeatedly picking out the smallest card and placing it in position. It is a comparison-based, in-place sorting algorithm that divides the array into a sorted and an unsorted region, repeatedly selecting the minimum element from the unsorted region and moving it to the end of the sorted region. Although its O(n²) time complexity makes it impractical for large datasets, I still find it valuable for teaching the fundamentals of algorithmic thinking and for niche cases where the number of swaps needs to be minimized.

History and Background

Selection sort does not have a single credited inventor the way some algorithms do — it emerged organically alongside other elementary sorting techniques (like bubble sort and insertion sort) during the earliest days of computer science, as programmers needed simple, understandable ways to order data with the limited memory and processing power available on early machines. It has been documented and analyzed extensively in classic algorithm texts since at least the 1960s, including Donald Knuth’s The Art of Computer Programming, which treats it as one of the foundational examples in the study of sorting algorithms.

Problem Statement

I need a straightforward way to sort a small dataset in place, using the minimum possible number of swap operations, even if that comes at the cost of a higher number of comparisons. Selection sort addresses this directly: it guarantees at most n-1 swaps for an array of size n, which matters in situations where write operations are significantly more expensive than read/compare operations, such as sorting data on flash memory.

Core Concepts

How It Works

I follow these repeating steps:

  1. I start with the entire array as the unsorted region and consider index 0 as the start of the unsorted region.
  2. I scan through the unsorted region to find the index of the minimum element.
  3. I swap that minimum element with the element at the start of the unsorted region.
  4. I move the boundary between sorted and unsorted regions one position to the right.
  5. I repeat this process until only one element remains in the unsorted region, at which point the array is fully sorted.

Working Principle

The logic behind selection sort is built on a simple invariant: after i passes, the first i elements of the array are the i smallest elements from the original array, arranged in sorted order, and they will never be touched again. I maintain this invariant by always searching only within the unsorted suffix for the next minimum, guaranteeing that once an element is placed into the sorted prefix, it stays there. This is what makes the algorithm easy to reason about, even though it is not the most efficient approach for large inputs.

Mathematical Foundation

For an array of size n, selection sort performs a fixed number of comparisons regardless of input order. On the i-th pass (0-indexed), I scan (n – i – 1) remaining elements to find the minimum. The total number of comparisons is:

$$\sum_{i=0}^{n-2} (n – i – 1) = \sum_{k=1}^{n-1} k = \frac{n(n-1)}{2}$$

This gives:

$$T(n) = O(n^2)$$

Unlike comparisons, the number of swaps is bounded tightly:

$$\text{Swaps} \leq n – 1$$

since selection sort performs at most one swap per pass, making it notably efficient in terms of write operations compared to algorithms like insertion sort or bubble sort, which can perform up to $O(n^2)$ swaps.

Diagrams

flowchart TD
    A[Start: Unsorted array] --> B[Set boundary at index 0]
    B --> C[Scan unsorted region for minimum element]
    C --> D[Swap minimum with element at boundary]
    D --> E[Move boundary one step right]
    E --> F{Boundary reached end minus one?}
    F -->|No| C
    F -->|Yes| G[Output: Sorted array]

Pseudocode

SELECTION-SORT(A)
    n = length(A)
    for i = 0 to n - 2
        minIndex = i
        for j = i + 1 to n - 1
            if A[j] < A[minIndex]
                minIndex = j
        if minIndex != i
            swap A[i] with A[minIndex]

Step-by-Step Example

I will sort [64, 25, 12, 22, 11].

Pass 1 (i=0): I scan indices 1–4 for the minimum. I find 11 at index 4. I swap A[0] and A[4] → [11, 25, 12, 22, 64]

Pass 2 (i=1): I scan indices 2–4 for the minimum. I find 12 at index 2. I swap A[1] and A[2] → [11, 12, 25, 22, 64]

Pass 3 (i=2): I scan indices 3–4 for the minimum. I find 22 at index 3. I swap A[2] and A[3] → [11, 12, 22, 25, 64]

Pass 4 (i=3): I scan index 4 for the minimum. I find 64, already the minimum among remaining elements, and since it equals the current minIndex, no swap occurs → [11, 12, 22, 25, 64]

Final sorted output: [11, 12, 22, 25, 64]

Time Complexity

I always point out that selection sort is one of the few algorithms whose performance is completely unaffected by how sorted the input already is — a property that can be either a drawback or a predictable guarantee, depending on the situation.

Space Complexity

Selection sort is fully in-place, requiring only O(1) additional space for temporary variables used during swaps. It does not need any auxiliary arrays, which makes it appealing in extremely memory-constrained environments despite its poor time complexity.

Correctness Analysis

I prove selection sort’s correctness using a loop invariant: at the start of each iteration of the outer loop, the subarray A[0..i-1] contains the i smallest elements of the original array, sorted in order. This holds trivially before the first iteration (i=0), since an empty subarray is trivially sorted. During each iteration, I find the true minimum of the remaining unsorted elements A[i..n-1] and swap it into position i, which extends the invariant to hold for A[0..i]. When the outer loop terminates after n-1 iterations, the invariant guarantees that A[0..n-2] holds the n-1 smallest elements sorted correctly, which forces the last remaining element A[n-1] to also be in its correct sorted position, proving the entire array is sorted.

Advantages

Disadvantages

Applications

Implementation in C

#include <stdio.h>

// Swap two integers
void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

// Selection sort implementation
void selectionSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int minIndex = i;

        // Find the minimum element in the unsorted region
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }

        // Swap only if a smaller element was found
        if (minIndex != i) {
            swap(&arr[i], &arr[minIndex]);
        }
    }
}

int main() {
    int arr[] = {64, 25, 12, 22, 11};
    int n = sizeof(arr) / sizeof(arr[0]);

    selectionSort(arr, n);

    printf("Sorted array: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    return 0;
}

Sample Input and Output

Input: [64, 25, 12, 22, 11]

Output: Sorted array: 11 12 22 25 64

Optimization Techniques

Common Mistakes

Further Reading

Exit mobile version