Selection Sort

Q: What is the time complexity of selection sort?

Selection sort is `O(n²)` in all cases - best, average, and worst - because it always scans the entire unsorted region to find each minimum. It uses `O(1)` extra space.

Q: What is the difference between selection sort and bubble sort?

Both are `O(n²)` comparison sorts, but selection sort makes at most `n-1` swaps while bubble sort can make up to `O(n²)` swaps. Bubble sort can also detect an already-sorted array and stop early, whereas selection sort always runs the full number of passes.

Last updated July 1, 2026

Selection sort divides the array into a sorted region on the left and an unsorted region on the right. On each pass it scans the unsorted region to find the smallest element, then swaps it into the first unsorted position - growing the sorted region by one. Press play above to watch the scan-and-swap, or step through it one comparison at a time.

Selection sort always does the same number of comparisons regardless of the input, but it performs at most n-1 swaps - far fewer than bubble sort - which can matter when writes are expensive.

Time & space complexity

Case	Complexity	Notes
Best case	O(n²)	Comparisons happen even if sorted
Average case	O(n²)	Random order
Worst case	O(n²)	Reverse-sorted
Space	O(1)	In-place
Stable	No	Swaps can reorder equal elements

Step by step

Step	What happens
1	Treat the whole array as unsorted.
2	Scan the unsorted region to find the minimum element.
3	Swap that minimum into the first unsorted position.
4	Move the boundary one step right (that slot is now sorted).
5	Repeat until only one element is unsorted.

Worked example

Sorting [5, 2, 4, 1]:

Pass	Array	Action
Start	`[5, 2, 4, 1]`	Whole array is unsorted.
1	`[1, 2, 4, 5]`	Scan `[5, 2, 4, 1]`, min is `1` at index 3; swap it with index 0.
2	`[1, 2, 4, 5]`	Scan `[2, 4, 5]`, min is `2` already at index 1; swap with itself.
3	`[1, 2, 4, 5]`	Scan `[4, 5]`, min is `4` already at index 2; no move needed.
Done	`[1, 2, 4, 5]`	Only `5` is left, so it is already in place.

When to use selection sort

Use it when	Avoid it when
Writes are expensive - it does at most `n-1` swaps.	The array is large - `O(n²)` comparisons dominate.
You need a simple, easy-to-implement in-place sort.	You need a stable sort that preserves the order of equal keys.
Memory is tight - it uses only `O(1)` extra space.	The data is nearly sorted - it cannot finish early like insertion sort.
The dataset is tiny and predictable performance matters.	Throughput matters - `O(n log n)` sorts like quicksort are far faster.

Selection Sort code

A clean, runnable Selection Sort implementation in Python, JavaScript, Java, C++, C. Pick a language, copy the code, or open it pre-loaded in the Coddy Playground.

Selection Sort code in PythonPython
1def selection_sort(a):2    n = len(a)3    for i in range(n - 1):4        # Find the smallest element in the unsorted tail5        min_idx = i6        for j in range(i + 1, n):7            if a[j] < a[min_idx]:8                min_idx = j9        a[i], a[min_idx] = a[min_idx], a[i]10    return a11
12
13nums = [64, 25, 12, 22, 11]14print("Before:", nums)15selection_sort(nums)16print("After: ", nums)
Run this code in the Python Playground

Selection Sort code in JavaScriptJavaScript
1function selectionSort(a) {2    for (let i = 0; i < a.length - 1; i++) {3        let min = i;4        // Find the smallest element in the unsorted tail5        for (let j = i + 1; j < a.length; j++) {6            if (a[j] < a[min]) min = j;7        }8        if (min !== i) [a[i], a[min]] = [a[min], a[i]];9    }10    return a;11}12
13const data = [5, 2, 9, 1, 7, 3];14console.log("Before:", data);15console.log("Sorted:", selectionSort([...data]));
Run this code in the JavaScript Playground

Selection Sort code in JavaJava
1import java.util.Arrays;2
3public class Main {4    static void selectionSort(int[] arr) {5        for (int i = 0; i < arr.length - 1; i++) {6            int minIndex = i;7            // Find the smallest value in the unsorted part8            for (int j = i + 1; j < arr.length; j++) {9                if (arr[j] < arr[minIndex]) minIndex = j;10            }11            int tmp = arr[i];12            arr[i] = arr[minIndex];13            arr[minIndex] = tmp;14        }15    }16
17    public static void main(String[] args) {18        int[] arr = {29, 10, 14, 37, 13, 5};19        System.out.println("Before: " + Arrays.toString(arr));20        selectionSort(arr);21        System.out.println("After:  " + Arrays.toString(arr));22    }23}
Run this code in the Java Playground

Selection Sort code in C++C++
1#include <iostream>2#include <utility>3#include <vector>4
5void printVec(const std::vector<int>& a) {6    for (int x : a) std::cout << x << " ";7    std::cout << "\n";8}9
10void selectionSort(std::vector<int>& a) {11    for (size_t i = 0; i + 1 < a.size(); ++i) {12        // Find the smallest element in the unsorted suffix13        size_t minIdx = i;14        for (size_t j = i + 1; j < a.size(); ++j) {15            if (a[j] < a[minIdx]) minIdx = j;16        }17        std::swap(a[i], a[minIdx]);18    }19}20
21int main() {22    std::vector<int> data = {29, 10, 14, 37, 13, 5};23    std::cout << "Before: ";24    printVec(data);25    selectionSort(data);26    std::cout << "After:  ";27    printVec(data);28    return 0;29}
Run this code in the C++ Playground

Selection Sort code in CC
1#include <stdio.h>2
3void printArr(const int a[], int n) {4    for (int i = 0; i < n; i++) printf("%d ", a[i]);5    printf("\n");6}7
8void selectionSort(int a[], int n) {9    for (int i = 0; i < n - 1; i++) {10        // Find the smallest element in the unsorted suffix11        int minIdx = i;12        for (int j = i + 1; j < n; j++) {13            if (a[j] < a[minIdx]) minIdx = j;14        }15        int tmp = a[i];16        a[i] = a[minIdx];17        a[minIdx] = tmp;18    }19}20
21int main(void) {22    int data[] = {29, 10, 14, 37, 13, 5};23    int n = sizeof(data) / sizeof(data[0]);24    printf("Before: ");25    printArr(data, n);26    selectionSort(data, n);27    printf("After:  ");28    printArr(data, n);29    return 0;30}
Run this code in the C Playground

Selection Sort FAQ

What is the time complexity of selection sort?

Selection sort is O(n²) in all cases - best, average, and worst - because it always scans the entire unsorted region to find each minimum. It uses O(1) extra space.

Is selection sort stable?

The standard in-place version is not stable, because swapping a distant minimum into place can move an equal element past another. A stable variant exists but requires shifting instead of swapping.

When is selection sort useful?

It is useful when the cost of writing to memory is high, since it performs at most n-1 swaps - the minimum possible for a comparison sort that moves elements.

What is the difference between selection sort and bubble sort?

Both are O(n²) comparison sorts, but selection sort makes at most n-1 swaps while bubble sort can make up to O(n²) swaps. Bubble sort can also detect an already-sorted array and stop early, whereas selection sort always runs the full number of passes.

Should I use selection sort or insertion sort?

Prefer insertion sort in most cases - it is stable, runs in O(n) on nearly-sorted data, and is faster on average. Choose selection sort only when minimizing the number of writes is the priority, since it guarantees at most n-1 swaps.

Why does selection sort always run in O(n²) even on a sorted array?

Selection sort has no way to know an element is already the minimum without scanning the rest of the unsorted region, so it performs every comparison on every pass regardless of input order. This means the best case equals the worst case at O(n²) - unlike insertion or bubble sort, which can short-circuit.

Related resources

More visualizations

Coddy programming languages illustration

Master algorithms with Coddy

GET STARTED