Selection Sort Algorithm Find Minimum Swap: Tutorial, Examples, FAQs & Interview Tips

What is Selection Sort?

Selection Sort is a simple comparison-based sorting algorithm. It repeatedly selects the smallest element from the unsorted part of the array and places it at the next correct position in the sorted part.

The array is conceptually divided into two parts:

a sorted portion on the left,
an unsorted portion on the right.

Key Insight: Selection Sort performs many comparisons but very few swaps. That is its main distinguishing feature among the basic quadratic sorting algorithms.

Core Idea

Start from the first position.
Find the minimum element in the remaining unsorted part.
Swap it with the current position.
Move one step right and repeat.

After each pass, one more element is guaranteed to be in its final correct position.

Why Selection Sort Is Always O(n^2)

Selection Sort always scans the unsorted portion to find the minimum element, even if the array is already sorted. That means the number of comparisons does not improve for best-case input.

The total comparisons are:

(n - 1) + (n - 2) + ... + 1 = n(n - 1)/2

So the time complexity remains O(n^2) in the best, average, and worst cases.

Time and Space Complexity

Metric	Best	Average	Worst	Space	Stable?
Time Complexity	O(n^2)	O(n^2)	O(n^2)	O(1)	No
Comparisons	Always n(n - 1) / 2			-	-
Swaps	At most n - 1			-	-

Comparisons vs Swaps

This is an important point:

Comparisons: always quadratic, because every pass searches the remaining unsorted portion.
Swaps: at most one useful swap per pass, so the total is only O(n).

This makes Selection Sort useful in situations where writing to memory is expensive but comparisons are relatively cheap.

How Selection Sort Works on an Example

Consider the array [29, 10, 14, 37, 13].

Pass 1: minimum is 10, swap with 29. Result: [10, 29, 14, 37, 13]
Pass 2: minimum is 13, swap with 29. Result: [10, 13, 14, 37, 29]
Pass 3: minimum is 14, already in correct place. Result: [10, 13, 14, 37, 29]
Pass 4: minimum is 29, swap with 37. Result: [10, 13, 14, 29, 37]

Selection Sort Implementation - Multiple Languages

import java.util.Arrays;

public class SelectionSort {

    static void selectionSort(int[] arr) {
        int n = arr.length;

        for (int i = 0; i < n - 1; i++) {
            int minIdx = i;

            for (int j = i + 1; j < n; j++) {
                if (arr[j] < arr[minIdx]) {
                    minIdx = j;
                }
            }

            if (minIdx != i) {
                int temp = arr[minIdx];
                arr[minIdx] = arr[i];
                arr[i] = temp;
            }
        }
    }

    static void selectionSortDesc(int[] arr) {
        int n = arr.length;

        for (int i = 0; i < n - 1; i++) {
            int maxIdx = i;
            for (int j = i + 1; j < n; j++) {
                if (arr[j] > arr[maxIdx]) {
                    maxIdx = j;
                }
            }

            int temp = arr[maxIdx];
            arr[maxIdx] = arr[i];
            arr[i] = temp;
        }
    }

    public static void main(String[] args) {
        int[] arr = {29, 10, 14, 37, 13};
        System.out.println("Before: " + Arrays.toString(arr));
        selectionSort(arr);
        System.out.println("After:  " + Arrays.toString(arr));

        int[] arr2 = {5, 3, 8, 1, 9};
        selectionSortDesc(arr2);
        System.out.println("Desc:   " + Arrays.toString(arr2));
    }
}

def selection_sort(arr):
    n = len(arr)

    for i in range(n - 1):
        min_idx = i
        for j in range(i + 1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j

        if min_idx != i:
            arr[i], arr[min_idx] = arr[min_idx], arr[i]

    return arr

def selection_sort_desc(arr):
    n = len(arr)

    for i in range(n - 1):
        max_idx = i
        for j in range(i + 1, n):
            if arr[j] > arr[max_idx]:
                max_idx = j

        arr[i], arr[max_idx] = arr[max_idx], arr[i]

    return arr

arr = [29, 10, 14, 37, 13]
print("Before:", arr)
selection_sort(arr)
print("After: ", arr)

#include 
#include 
using namespace std;

void selectionSort(vector& arr) {
    int n = arr.size();

    for (int i = 0; i < n - 1; i++) {
        int minIdx = i;
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIdx]) {
                minIdx = j;
            }
        }

        if (minIdx != i) {
            swap(arr[i], arr[minIdx]);
        }
    }
}

int main() {
    vector arr = {29, 10, 14, 37, 13};
    selectionSort(arr);
    for (int x : arr) cout << x << " ";
    return 0;
}

function selectionSort(arr) {
    const n = arr.length;

    for (let i = 0; i < n - 1; i++) {
        let minIdx = i;
        for (let j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIdx]) {
                minIdx = j;
            }
        }

        if (minIdx !== i) {
            [arr[i], arr[minIdx]] = [arr[minIdx], arr[i]];
        }
    }

    return arr;
}

let arr = [29, 10, 14, 37, 13];
console.log("Before:", arr);
selectionSort(arr);
console.log("After: ", arr);

Detailed Step-by-Step Trace

Pass	Current Position	Minimum Found	Action	Array After Pass
1	0	10	Swap with 29	`[10, 29, 14, 37, 13]`
2	1	13	Swap with 29	`[10, 13, 14, 37, 29]`
3	2	14	No swap needed	`[10, 13, 14, 37, 29]`
4	3	29	Swap with 37	`[10, 13, 14, 29, 37]`

Why Selection Sort Is Not Stable

Selection Sort is generally not stable because swapping the minimum element with the current position can change the relative order of equal elements.

For example, if equal values carry hidden labels such as 5a and 5b, a swap may move 5b before 5a, changing their original order.

Why Selection Sort Is In-Place

Selection Sort needs only a constant number of extra variables such as indices and a temporary swap variable. It does not require extra arrays, so its space complexity is O(1).

Selection Sort vs Bubble Sort vs Insertion Sort

Feature	Selection Sort	Bubble Sort	Insertion Sort
Best case	O(n^2)	O(n)	O(n)
Average / Worst	O(n^2)	O(n^2)	O(n^2)
Stable	No	Yes	Yes
Number of swaps	Small	Can be many	Usually many shifts
Best use case	When writes are expensive	Educational use	Small or nearly sorted data

When to Use Selection Sort

Write-limited systems: useful when memory writes are expensive.
Small arrays: acceptable for tiny inputs where simplicity matters.
Educational settings: helpful for learning sorting logic and algorithm analysis.
Memory-constrained environments: good when only O(1) extra space is available.

When Not to Use Selection Sort

For large datasets, because O(n^2) becomes too slow.
For nearly sorted data, because Insertion Sort performs better.
When stable sorting is required.
When average-case performance matters more than swap count.

Advantages of Selection Sort

Simple to understand and implement.
In-place with O(1) space.
Uses relatively few swaps.
Performance is predictable because it behaves similarly on all inputs.

Limitations of Selection Sort

Always takes O(n^2) time.
Not stable.
Does not benefit from already sorted or nearly sorted input.
Usually slower than better algorithms on medium and large arrays.

Common Mistakes

Assuming fewer swaps means better overall speed. Comparisons still dominate.
Thinking Selection Sort improves on sorted input. It does not.
Confusing Selection Sort with Insertion Sort.
Assuming it is stable.

Key Takeaways

Selection Sort repeatedly selects the minimum element from the unsorted part.
Its time complexity is always O(n^2).
Its main advantage is the small number of swaps.
It is in-place but not stable.
It is mostly useful for small inputs, educational purposes, or write-sensitive systems.

Previous Next