DSA Complexity

Selection sort cost

Scene: a device where writes wear memory. Selection sort's comparisons never blink; its swaps barely move.

Selection sort always pays and at most . In-place, typically unstable, not adaptive.

Algorithm journey

n-1 passes

Each commits one final minimum.

Full suffix scan

No early exit in the standard form.

Optional swap

O(1) writes per pass.

Sum the triangle

Comparisons = n(n-1)/2 exactly for the classic loops.

What actually happens

Naive claim: fewer swaps mean faster asymptotically. No: comparisons still dominate Theta(n^2).

Better claim: use when writes dominate cost at tiny n.

Large n: prefer Theta(n log n) comparison sorts or domain sorts.

Invariant

After i passes, i positions are final; the remaining comparisons are still forced by the algorithm's nested loops.

How to read selection sort's complexity

1. Write-sensitive tiny arrays? Maybe.

2. Need adaptivity/stability? No.

3. Teaching nested loops? Yes.

Quantitative check

n = 10,000: exactly 49,995,000 comparisons, at most 9,999 swaps, independent of input order.

How it works

Find Minimum in Unsorted Region

Scan through the unsorted portion to find the smallest element.

Swap with First Unsorted Element

Swap the minimum with the first element of the unsorted region.

Expand Sorted Region

The sorted region grows by one element, unsorted region shrinks by one.

Repeat Until Done

Continue until the entire array is sorted (unsorted region is empty).

Note: Minimum Number of Swaps

Selection sort makes at most n-1 swaps (one per pass), regardless of input! This is fewer swaps than bubble sort, which can make O(n²) swaps. If swapping is expensive (e.g., large objects or writing to slow memory), selection sort can be more efficient than bubble sort despite similar time complexity!

🎯 Visual Example

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

Pass 1:

[64, 25, 12, 22, 11] ← Find min in unsorted

Min = 11 (at index 4)

Swap 64 ↔ 11

[11 | 25, 12, 22, 64] ← 11 sorted!

Pass 2:

[11 | 25, 12, 22, 64] ← Find min in unsorted

Min = 12 (at index 2)

Swap 25 ↔ 12

[11, 12 | 25, 22, 64] ← 12 sorted!

Pass 3:

[11, 12 | 25, 22, 64] ← Find min in unsorted

Min = 22 (at index 3)

Swap 25 ↔ 22

[11, 12, 22 | 25, 64] ← 22 sorted!

Pass 4:

[11, 12, 22 | 25, 64] ← Find min in unsorted

Min = 25 (already in place)

No swap needed

[11, 12, 22, 25 | 64] ← 25 sorted!

Final: [11, 12, 22, 25, 64] ✓ Sorted!

🎮 Interactive Selection Sort Demo

Click "Start" to watch the algorithm find the smallest bar and swap it into place!

Speed:

ℹ️ Ready

Comparing/Active

Sorted

🎯 Key Insight: Always O(n²), No Matter What!

Unlike bubble sort which can be O(n) for sorted arrays, selection sort always makes the same number of comparisons: n + (n-1) + (n-2) + ... + 1 = n(n-1)/2 ≈ O(n²). Whether the array is sorted, reverse-sorted, or random, selection sort takes the same time! This makes it not adaptive - it doesn't benefit from partially sorted data.

💻 Implementation

Python

python

def selection_sort(arr):
    """
    Selection Sort - Select minimum and place it in sorted region
    
    Time Complexity:
    - Best Case: O(n²) - always same comparisons
    - Average Case: O(n²)
    - Worst Case: O(n²)
    
    Space Complexity: O(1) - in-place sorting
    
    Properties:
    - NOT stable (can change relative order of equal elements)
    - NOT adaptive (doesn't benefit from sorted data)
    - In-place (O(1) extra space)
    - Minimum swaps (at most n-1)
    """
    n = len(arr)
    
    # Outer loop: position to fill in sorted region
    for i in range(n - 1):
        # Assume first unsorted element is minimum
        min_idx = i
        
        # Inner loop: find actual minimum in unsorted region
        for j in range(i + 1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
        
        # Swap minimum with first unsorted element
        # Only swap if minimum is not already in place
        if min_idx != i:
            arr[i], arr[min_idx] = arr[min_idx], arr[i]
    
    return arr


# Example Usage
arr = [64, 25, 12, 22, 11]
print(f"Original: {arr}")

sorted_arr = selection_sort(arr.copy())
print(f"Sorted: {sorted_arr}")

# Output:
# Original: [64, 25, 12, 22, 11]
# Sorted: [11, 12, 22, 25, 64]

Java

java

public class SelectionSort {
    /**
     * Selection Sort - Select minimum and place it in sorted region
     * 
     * Time Complexity:
     * - Best Case: O(n²) - always same comparisons
     * - Average Case: O(n²)
     * - Worst Case: O(n²)
     * 
     * Space Complexity: O(1) - in-place sorting
     */
    public static void selectionSort(int[] arr) {
        int n = arr.length;
        
        // Outer loop: position to fill in sorted region
        for (int i = 0; i < n - 1; i++) {
            // Assume first unsorted element is minimum
            int minIdx = i;
            
            // Inner loop: find actual minimum in unsorted region
            for (int j = i + 1; j < n; j++) {
                if (arr[j] < arr[minIdx]) {
                    minIdx = j;
                }
            }
            
            // Swap minimum with first unsorted element
            // Only swap if minimum is not already in place
            if (minIdx != i) {
                int temp = arr[minIdx];
                arr[minIdx] = arr[i];
                arr[i] = temp;
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = {64, 25, 12, 22, 11};
        System.out.println("Original: " + java.util.Arrays.toString(arr));
        
        selectionSort(arr);
        
        System.out.println("Sorted: " + java.util.Arrays.toString(arr));
    }
}

Invariant and correctness

Prefix invariant: before iteration i, positions [0, i) contain the i smallest input values in sorted order. Scanning [i, n) finds its minimum; swapping that minimum into i establishes the invariant for i+1. When i reaches n−1, only one value remains, so the entire array is sorted.

The usual swap breaks stability. For example, moving a later minimum over an earlier equal-key record can reverse those records. A stable variant removes the minimum and shifts the intervening range right, trading the low-write advantage for Θ(n²) moves. The standard algorithm is in-place, non-adaptive, and offline because it must inspect the entire remaining region before it can certify the next minimum.

Exact cost model

Comparisons

Always n(n−1)/2 key comparisons, regardless of whether the input is sorted, random, or reversed.

Writes

At most n−1 swaps. This can matter when writes are much more expensive than reads; it does not make scans cheap.

Partial selection

Stopping after k passes costs Θ(kn), but a heap or linear-time selection algorithm is usually better for top-k.

⚡ Complexity Analysis

Time Complexity

⚠
O(n²) - Best Case
Always scans entire unsorted region
⚠
O(n²) - Average Case
n(n-1)/2 comparisons always
⚠
O(n²) - Worst Case
Same as best/average - not adaptive!

Space Complexity

✓
O(1)
In-place, only temp variable for swapping

Other Properties

✗NOT Stable: Can change order of equal elements
✗NOT Adaptive: Doesn't benefit from sorted data
✓In-place: O(1) extra space
✓Minimum swaps: At most n-1 swaps

Tip: When Selection Sort Shines

Selection sort is useful in specific scenarios:

• Write-sensitive buffers: At most n−1 swaps, while still paying n(n−1)/2 reads/comparisons
• Tiny bounded arrays: Simple, deterministic control flow can be useful after measurement
• Expensive movement: Sort compact references or indices; do not repeatedly copy heavyweight records
• Partial output: k passes produce the k smallest in Θ(kn), though heaps or quickselect scale better

Avoid when: You need stability, have large datasets, or data is nearly sorted!

✅ Pros & ❌ Cons

✅ Advantages

✓Simple to understand and implement
✓In-place sorting (O(1) extra space)
✓Minimum number of swaps (at most n-1)
✓Performs well when swapping is expensive
✓Predictable performance (always O(n²))
✓Can stop after k passes when k and n are both tightly bounded

❌ Disadvantages

✗O(n²) time complexity - slow for large arrays
✗NOT stable (changes order of equal elements)
✗NOT adaptive (no benefit from sorted data)
✗Always makes same comparisons (can't optimize)
✗Worse than insertion sort for nearly-sorted data

💼 Real World Applications

💾 Write-sensitive arrays

Selection sort minimizes array swaps, which can help when element movement is more expensive than comparison. Sorting an in-memory buffer does not automatically translate into fewer persistent-storage writes; measure the actual layer.

Model reads, comparisons, swaps, and the cost of one moved element separately.

🎯 Finding Top K Elements

Running k selection passes costs Θ(kn) and returns a sorted prefix. A size-k heap costs O(n log k), while quickselect gives expected O(n) partitioning when the prefix itself need not be sorted.

Example: Finding top 10 scores from 100

🔧 Embedded Controllers

A controller with a strict small input bound may value predictable comparisons and O(1) auxiliary space. The bound and deadline should be proved; limited RAM alone does not distinguish selection sort from other in-place sorts.

Example: Arduino sorting 10 sensor readings

📚 Educational Demonstrations

Selection sort's clear "select minimum and swap" pattern makes it excellent for teaching algorithm concepts and demonstrating how sorting works step-by-step.

Example: CS education and algorithm visualization

Engineering contract and verification

The implementation mutates the array and is not stable. Say both in the API; callers doing multi-key sorting may depend on stability.
Comparing heavyweight records repeatedly can dominate runtime. Cache keys or sort references/indices rather than copying large objects.
Python tuple comparison is lexicographic; Java comparators should use Integer.compare, not subtraction that can overflow.
Test sortedness and multiset preservation on empty, singleton, duplicates, extremes, sorted, reverse, and randomized arrays. Instrument comparisons to verify n(n−1)/2 exactly.

Use selection sort only when n is strictly small and bounded or writes are unusually constrained. For top-k, prefer a size-k heap when k is small, quickselect for an unordered cutoff, or the platform's optimized sort when all output is needed.

Exercises

Show the exact comparison count formula from the loop bounds.
Can a modified selection be adaptive without losing the write bound? Discuss trade-offs.
Compare selection vs insertion on already-sorted input for both compares and writes.

Primary sources

CLRS elementary sorts.
Knuth TAOCP Vol. 3: selection sorting.
Sedgewick & Wayne: empirical elementary-sort plots.

Short takeaway

Selection Sort = Find minimum in unsorted region, swap with first unsorted element, repeat.Time: Always O(n²) - not adaptive.Space: O(1) in-place.Swaps: At most n-1 (minimum possible).Properties: NOT stable, NOT adaptive, simple.Use when: Swaps are expensive, small datasets, or finding k smallest.Avoid when: Need stability or have large/nearly-sorted data!