Sorting
Selection sort vs Quick sort
Selection sort and Quick sort both put an array in order, in different ways. Selection sort: repeatedly pick the smallest remaining value. Quick sort: divide and conquer: partition around a pivot. In the worst case both take O(n²), so the choice comes down to the other differences below.
At a glance
| Property | Selection sort | Quick sort |
|---|---|---|
| Technique | Repeatedly pick the smallest remaining value | Divide and conquer: partition around a pivot |
| Best case time | O(n²) | O(n log n) |
| Average case time | O(n²) | O(n log n) |
| Worst case time | O(n²) | O(n²) |
| Extra space | O(1) | O(log n) |
| Stable (equal values keep their order) | No | No |
| In place (no extra array) | Yes | Yes |
| 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 quick sort when
you want a fast in-place sort on typical data.
Avoid it when
you need a worst-case guarantee or a stable sort.
The same inputs, counted
These numbers come from running both real implementations: operations (comparisons plus writes, a swap counting as two writes).
| Input | Selection sort | Quick sort |
|---|---|---|
| Mixed | 29 | 31 |
| Already sorted | 21 | 75 |
| Reversed | 27 | 51 |
| Nearly sorted | 23 | 65 |
| Duplicates | 31 | 29 |
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 Heap sort
- Selection sort vs Counting 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