Selection Sort: Introduction and Program

What is Selection Sort?

Selection sort is a simple way to sort a list. It is easy to understand and easy to code. The main idea is: repeatedly find the smallest item and put it at the front of the list.

It works in-place (it does not need extra big memory) and has a time complexity of O(n²). This means it is fine for small lists but slow for very large lists.

Simple Analogy: Picking the Smallest Card

Imagine you have a row of cards. To sort them from small to big:

Look through all the cards. Find the smallest one.
Swap it with the first card.
Now ignore the first card (because it is in the right place).
Repeat: find the smallest card in the rest, swap it into the next position.
Keep going until all cards are in order.

How Selection Sort Works (Step by Step)

Start at position i = 0 (the first element).
Find the minimum value in the range i to end.
Swap that minimum value with the value at position i.
Move to i = i + 1 and repeat until the list is sorted.

Walk-through Example

We sort this list: [64, 25, 12, 22, 11]

i = 0: min in [64, 25, 12, 22, 11] is 11. Swap with 64 → [11, 25, 12, 22, 64]
i = 1: min in [25, 12, 22, 64] is 12. Swap with 25 → [11, 12, 25, 22, 64]
i = 2: min in [25, 22, 64] is 22. Swap with 25 → [11, 12, 22, 25, 64]
i = 3: min in [25, 64] is 25. Swap with 25 (no change) → [11, 12, 22, 25, 64]
i = 4: only one element left, done.

Programs in Popular Languages

Python

def selection_sort(arr):
    n = len(arr)
    for i in range(n - 1):
        min_index = i
        # Find index of the smallest element in the unsorted part
        for j in range(i + 1, n):
            if arr[j] < arr[min_index]:
                min_index = j
        # Swap if a smaller element was found
        if min_index != i:
            arr[i], arr[min_index] = arr[min_index], arr[i]
    return arr

# Example usage
nums = [64, 25, 12, 22, 11]
print(selection_sort(nums))  # Output: [11, 12, 22, 25, 64]

C

#include <stdio.h>

void selection_sort(int a[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int min_index = i;
        for (int j = i + 1; j < n; j++) {
            if (a[j] < a[min_index]) {
                min_index = j;
            }
        }
        if (min_index != i) {
            int temp = a[i];
            a[i] = a[min_index];
            a[min_index] = temp;
        }
    }
}

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

    selection_sort(arr, n);

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

Java

public class SelectionSortExample {
    public static void selectionSort(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n - 1; i++) {
            int minIndex = i;
            for (int j = i + 1; j < n; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }
            if (minIndex != i) {
                int temp = arr[i];
                arr[i] = arr[minIndex];
                arr[minIndex] = temp;
            }
        }
    }

    public static void main(String[] args) {
        int[] data = {64, 25, 12, 22, 11};
        selectionSort(data);
        for (int x : data) {
            System.out.print(x + " ");
        }
    }
}

JavaScript

function selectionSort(arr) {
  const n = arr.length;
  for (let i = 0; i < n - 1; i++) {
    let minIndex = i;
    for (let j = i + 1; j < n; j++) {
      if (arr[j] < arr[minIndex]) {
        minIndex = j;
      }
    }
    if (minIndex !== i) {
      [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]]; // swap
    }
  }
  return arr;
}

// Example
console.log(selectionSort([64, 25, 12, 22, 11])); // [11, 12, 22, 25, 64]

Pseudocode (Easy to Read)

for i from 0 to n-2:
    min_index = i
    for j from i+1 to n-1:
        if A[j] < A[min_index]:
            min_index = j
    if min_index != i:
        swap A[i] and A[min_index]

Time and Space Complexity

Time: O(n²) in best, average, and worst cases (because we always scan the rest of the list).
Space: O(1) extra space (it is in-place).
Stability: Not stable by default (equal items may change order after swaps).

Properties

In-place: Yes.
Stable: No (unless modified with shifting instead of swapping).
Deterministic: Yes (no randomness).
Comparison-based: Yes.

Advantages

Very simple to learn and implement.
Needs few swaps (at most n − 1 swaps).
Works well when swaps are expensive but comparisons are cheap.
Good for small arrays or nearly sorted arrays when swap cost matters.

Disadvantages

Slow for large lists: O(n²).
Not stable without extra logic.
Always does the same number of comparisons, even if the list is already sorted.

Where Is Selection Sort Used?

Teaching sorting basics.
Sorting very small datasets.
Cases where you want to minimize swaps (for example, memory writes are costly).
Getting the k smallest elements by doing only k passes.

Edge Cases to Consider

Empty list: do nothing.
One element: already sorted.
Already sorted list: still O(n²) comparisons, but minimal swaps.
Reverse sorted list: same O(n²).
Duplicates: works fine, but order of equal items may change (not stable).
Negative numbers: works fine.

Sorting in Descending Order

To sort from largest to smallest, pick the maximum each time instead of the minimum, and swap it to the front.

def selection_sort_desc(arr):
    n = len(arr)
    for i in range(n - 1):
        max_index = i
        for j in range(i + 1, n):
            if arr[j] > arr[max_index]:
                max_index = j
        if max_index != i:
            arr[i], arr[max_index] = arr[max_index], arr[i]
    return arr

Common Mistakes and Tips

Forgetting to reset the min_index at each outer loop step.
Swapping too early: swap only after the inner loop finishes.
Unneeded swap: check if min_index != i before swapping.
Off-by-one errors: outer loop runs to n – 2, inner loop starts at i + 1.

Practice Task

Use the Python (or any) code to sort: [29, 10, 14, 37, 13].
Write down the list after each outer loop pass.
Try changing the code to sort in descending order.

Now you know how selection sort works and how to code it in multiple languages!