Swap your way along
Walk the list once, swapping any pair that's out of order. About 8 minutes.
Compare two neighbours, then maybe swap
Picture two kids standing side by side in a height line. If the left one is taller, they swap places, so the shorter one ends up first. If the left one is already shorter, or they are the same height, nobody moves and you step on.
That is the whole move: look at a neighbouring pair, and swap only if they are out of order.
5 and 1: 5 is bigger, so swap.
One pass, one walk to the end
Start at the front of the line and walk right, comparing and swapping as you go, all the way to the last pair. That is one pass. It doesn't fully sort the list, but every swap pushes a bigger value one step closer to the end, and the very biggest value gets carried all the way there.
for i in range(len(nums) - 1):
if nums[i] > nums[i + 1]:
nums[i], nums[i + 1] = \
nums[i + 1], nums[i]
return numsnums = [3, 8, 1, 6]. What does nums look like after one bubble-sort pass, left to right?
- A[3, 1, 6, 8]
- B[1, 3, 6, 8]
- C[3, 8, 1, 6]
Show the answer
[3, 1, 6, 8]. 3 and 8 don't swap. 8 and 1 swap, then 8 and 6 swap: 8 slides one step at a time until the pass ends.
One bubble pass
A bubble-sort pass walks nums from left to right. At each position i (from 0 to the second-to-last), it compares nums[i] with nums[i + 1]; if the left value is bigger, it swaps them, using the values already updated by earlier swaps in this same pass. Return nums after exactly one such pass.
nums = [5, 1, 4, 2, 8] → [1, 4, 2, 5, 8]
0 ≤ n ≤ 100,000 · −1,000,000,000 ≤ each value ≤ 1,000,000,000