Complexity Analysis
Selection sort has consistent performance regardless of input.
Time Complexity
All Cases: O(n²)
- Best case: O(n²) - still scans all elements
- Average case: O(n²) - same number of comparisons
- Worst case: O(n²) - same as best case
Total comparisons: n(n-1)/2
Visualizing Complexity
Space Complexity
O(1) - Constant Space
- Only uses a few variables
- Sorts in-place
- No additional arrays needed
Comparison with Other Algorithms
| Algorithm | Best | Average | Worst | Space | Swaps |
|---|---|---|---|---|---|
| Selection Sort | O(n²) | O(n²) | O(n²) | O(1) | O(n) |
| Bubble Sort | O(n) | O(n²) | O(n²) | O(1) | O(n²) |
| Insertion Sort | O(n) | O(n²) | O(n²) | O(1) | O(n²) |
Selection sort makes fewer swaps than bubble sort but always does the same comparisons.
Advantages
- Simple to understand and implement
- Makes minimum number of swaps (O(n))
- In-place sorting
- Consistent performance
Disadvantages
- Always O(n²) - no best case optimization
- Not stable
- Slower than O(n log n) algorithms
- Not adaptive
When Input Size Doubles
- n = 10: ~45 comparisons
- n = 20: ~190 comparisons (4x more)
- n = 40: ~780 comparisons (16x more)
Performance degrades quadratically.
What’s Next?
Let’s compare selection sort with other sorting algorithms.
Progress 71%
Page 5 of 7
← Previous
→ Next