Where it runs
1. The problem
You have a short list of numbers in no particular order, and you want them from small to large. In selection sort you could swap any two cells, even ones far apart.
Here the rule is tighter. You may only compare two numbers that sit next to each other. The only move you have is to swap that pair. You can't jump over cells. This lesson shows that these swaps are still enough to sort the whole list.
Say a leaderboard holds [5, 1, 4, 2, 8], and you want [1, 2, 4, 5, 8]. At each step you look at one pair of neighbours and swap it if it is in the wrong order.
This step is part of the paid track
The first 33 steps are open to everyone: lesson, exercise and tests. This one opens with full access. Start with a free account and the free steps.
Create a free accountSee what is includedRecognise it
Say these words and it is this pattern
- n is small (tens or a few hundred)
- array is nearly sorted already
- sort in place with O(1) extra space
- teaching/interview question about how sorting works
- stability matters and simplicity is fine
Looks similar, isn't
- Fast sort (merge / quick)
Merge and quick sort split the array and cost n log n. These three never split anything.
- Non-comparison sort (counting / radix)
Counting sort reads the values instead of comparing them. That needs a small range of keys.
- Sort with a custom comparator
That page is about which order you want. This one is about how the order is produced.
- Binary heap / priority queue
Selection sort scans for the smallest value every round. A heap hands it over in log n.
n up to roughly 5000 is fine at O(n squared). Insertion sort drops to O(n) on nearly sorted data.
On LeetCode
Problems where only neighbours are compared, such as checking that a list is in order or sorting a short list by swapping adjacent items. A pass with no wrong pair proves the list is sorted.
One pass over neighbour pairs, checking that none goes up or that none goes down.
Count the neighbour pairs in the wrong order, the last and first included, and allow at most one.
At most 250 rows, so bubble whole rows by their kth score from high to low.