Selection Sort
- Ω( n2 )
- Θ( n2 )
- O( n2 )
- space O( 1 )
Array
Comparator strip
Index down, time to the right
- Comparisons count only element-against-element checks; loop and index checks are never counted.
- Reads and writes include reads and writes to helper buffers (merge, counting, radix, bucket and tim sort).
- A swap counts once, as a swap. It is never also counted as a read or a write.
- Real time is the average time of the counted sort on this device over repeated runs, measured once before playback and independent of animation speed. Visual time is the time spent animating, excluding pauses.
How selection sort works
Selection Sort is a simple sorting algorithm that repeatedly selects the smallest element from the unsorted list and places it at the end of the sorted list. This process is repeated until all the elements are sorted.
Selection Sort has a time complexity of O(n²) which makes it inefficient for large data sets, but it is a simple algorithm to understand and implement.
Read more
It performs at most one swap per pass, so it writes far less than bubble sort even though it compares just as often.
| Best time | Ω( n2 ) | poor |
|---|---|---|
| Average time | Θ( n2 ) | poor |
| Worst time | O( n2 ) | poor |
| Worst space | O( 1 ) | good |
Big O notation gives the lower, average and upper bounds of an algorithm. Time complexity bounds the number of operations; space complexity bounds the extra memory it uses.