Sorting
Selection sort vs Counting sort
Selection sort and Counting sort both put an array in order, in different ways. Selection sort: repeatedly pick the smallest remaining value. Counting sort: count each value, turn the counts into positions and place the values, with no comparisons. Counting sort compares no values: it takes O(n + k), where k is the number of possible values (or digit values) and d the number of digits (radix sort), while selection sort takes O(n²) in the worst case. Counting sort is faster only when k and d are small compared with n; selection sort makes no assumption about the values.
At a glance
| Property | Selection sort | Counting sort |
|---|---|---|
| Technique | Repeatedly pick the smallest remaining value | Count each value, turn the counts into positions and place the values, with no comparisons |
| Compares values with each other | Yes | No |
| Best case time | O(n²) | O(n + k) |
| Average case time | O(n²) | O(n + k) |
| Worst case time | O(n²) | O(n + k) |
| Extra space | O(1) | O(n + k) |
| Stable (equal values keep their order) | No | Yes |
| In place (no extra array) | Yes | No |
| Needs sorted input | No | No |
When to choose each
Choose selection sort when
writing to memory is expensive, since it makes at most n - 1 swaps.
Avoid it when
the data is large, or you hope sorted input will be fast.
Choose counting sort when
the values are whole numbers in a range k that is small compared with n.
Avoid it when
the range of values is large, or the values are not whole numbers.
The same inputs, counted
These numbers come from running both real implementations: operations (comparisons plus writes, a swap counting as two writes). Counting sort makes no comparisons, so its count is writes only. It includes the k + 1 cells of the count array.
| Input | Selection sort | Counting sort |
|---|---|---|
| Mixed | 29 | 47 |
| Already sorted | 21 | 47 |
| Reversed | 27 | 47 |
| Nearly sorted | 23 | 47 |
| Duplicates | 31 | 47 |
See them run
More comparisons
- Bubble sort vs Selection sort
- Bubble sort vs Insertion sort
- Bubble sort vs Merge sort
- Bubble sort vs Quick sort
- Bubble sort vs Heap sort
- Bubble sort vs Counting sort
- Bubble sort vs Radix sort
- Selection sort vs Insertion sort
- Selection sort vs Merge sort
- Selection sort vs Quick sort
- Selection sort vs Heap sort
- Selection sort vs Radix sort
- Insertion sort vs Merge sort
- Insertion sort vs Quick sort
- Insertion sort vs Heap sort
- Insertion sort vs Counting sort
- Insertion sort vs Radix sort
- Merge sort vs Quick sort
- Merge sort vs Heap sort
- Merge sort vs Counting sort
- Merge sort vs Radix sort
- Quick sort vs Heap sort
- Quick sort vs Counting sort
- Quick sort vs Radix sort
- Heap sort vs Counting sort
- Heap sort vs Radix sort
- Counting sort vs Radix sort