Overview
Selection Sort scans the unsorted part of the list, finds the minimum value, and swaps it into the next sorted position.
CoreSource checked
Selection Sort
Sorts by repeatedly selecting the smallest remaining item.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Sorting
- Difficulty
- Beginner
- Family
- Selection Sort
- Tier
- Core
- Status
- Verified
- Review
- Source Checked
- Sources
- 1
- Formulas
- 0
- Relationships
- 4
- Code example
- Ready
- Visualization
- Ready
Core Concepts
comparison rulein-place updateselection sortordering invariantcomparison or key rulearray rearrangement
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(n^2)
Average
O(n^2)
Worst
O(n^2)
Space
O(1)
When to Use
- Use Selection Sort when you need to find the smallest unsorted value.
- Use it for teaching simple sorting with inputs like array or list of comparable values.
- Use it when ordered output makes later searching, ranking, or presentation easier.
- Use it when the Selection Sort tradeoff is acceptable for the problem size.
When Not to Use
- Avoid it when a partial order, top-k result, or streaming approach would answer the question with less work.
- Avoid it when O(n^2) worst-case behavior is too costly for the expected input size.
- Avoid it when the required output is not sorted array or list.
What It Does
- Finds the smallest unsorted value
- Places selected values at the front
Use Cases
- Teaching simple sorting
- Sorting when swaps are costly
- Small fixed-size lists
Inputs
- Array or list of comparable values
Outputs
- Sorted array or list
Pseudocode
- 1.Start with an empty sorted prefix
- 2.Scan the unsorted suffix for the smallest value
- 3.Swap that value into the next sorted position
- 4.Move the boundary between sorted and unsorted values
- 5.Repeat until the list is sorted
Canonical Example
- Input
- values = [5, 1, 4, 2]
- Output
- values = [1, 2, 4, 5]
- Explanation
- Selection Sort: The algorithm reorders the values so later operations can read them in ascending order.
Implementation Notes
- Keep the input contract explicit: Array or list of comparable values.
- Use this step as the implementation spine: Start with an empty sorted prefix.
- Then preserve the next state change: Scan the unsorted suffix for the smallest value.
- Test with empty input, one item, duplicates, and already sorted values.
Common Pitfalls
- Selection Sort makes few swaps, but it still performs many comparisons.
- Forgetting to define how equal values and custom comparison rules should behave.
- Returning sorted array or list without handling empty, invalid, or boundary inputs.
Interactive Mechanism Walkthrough
Array Partition & Ordering TraceHighlight the current minimum while the unsorted range is scanned.
38[0]
14[1]
52[2]
23[3]
61[4]
19[5]
44[6]
29[7]
Step 1 of 5: Start with an empty sorted prefix
array-selectionNotes
Selection Sort operates in O(n^2) time and O(1) space within the Selection Sort family. Often compared with Bubble Sort and Heap Sort.
Sources (1)
What each reference supports for this entry.
Introduction to Algorithms (CLRS)
BookTextbook support for Selection Sort invariants, recurrences, relaxation rules, or asymptotic analysis.
Open sourceExplore Next
Good next jumps from the relationship graph, ranked for useful discovery.
AlternativesInsertion Sort
Sorting · Foundation
Both are simple quadratic sorts, but insertion sort adapts better to nearly sorted data.
Compare with thisAlternative toBubble Sort
Sorting · Core
Selection sort reduces swaps compared with bubble sort while keeping quadratic comparison cost.
Compare with thisRelationships
View full relationship pageAlternative toBubble Sort
Selection sort reduces swaps compared with bubble sort while keeping quadratic comparison cost.
Related Algorithms
Tags
Comparison SortIn PlaceClassic