Selection Sort: Analysis
You'll learn why selection sort always performs the same number of comparisons, no matter what the data looks like, and why it doesn't preserve the relative order of equal elements.
Understanding Selection Sort's Behavior
Unlike bubble sort, which can finish early on sorted data, selection sort doesn't adapt to the input. It always scans the entire unsorted portion to find the minimum element, even if the array is already sorted. This means it performs exactly the same number of comparisons regardless of the initial order.
Time Complexity: Always O(n²)
Selection sort makes n-1 passes. On each pass i, it compares the current element with all remaining elements:
- Pass 1: (n-1) comparisons
- Pass 2: (n-2) comparisons
- ...
- Pass n-1: 1 comparison
Total: (n-1) + (n-2) + ... + 1 = n(n-1)/2 comparisons
This gives O(n²) time complexity in all cases—best, worst, and average. There's no early exit, no optimization possible based on data patterns.
Space Complexity: O(1)
Selection sort is in-place, using only a constant amount of extra memory for temporary variables during swaps.
Stability Issue
Selection sort is unstable. When you swap the minimum element with the current position, you can move it past equal elements, disrupting their original order. For example, with two 5s marked as 5₁ and 5₂, selection sort might place 5₂ before 5₁ even though 5₁ came first.
Key Takeaway: Selection sort consistently runs in O(n²) time with O(1) space, making it in-place but unstable, and it shows no performance improvement on nearly-sorted data.