Sorting Simple sorts
144. Bubble Sort
You are given an array of integers nums. Sort it in ascending order, smallest first, using bubble sort.
Bubble sort works in passes. Each pass walks the array from left to right, compares each element with its right neighbour, and swaps the two when the left one is larger. The passes repeat until the array is sorted.
Change nums itself. The function returns nothing; the answer is what nums holds after it finishes. Every
copy of a repeated value stays, so equal values end up next to each other.
Write the sort yourself. Do not call your language's built-in sort, such as std::sort, Arrays.sort,
list.sort or Array.prototype.sort. Aim to stop as soon as the array is sorted, so that an array already
in order takes a single pass.
Example 1
Input: nums = [6, -3, 8, 1, 2]
[-3,1,2,6,8]Explanation: The first pass carries 8 to the end, and the second carries 6 next to it. The third pass makes no swaps, so the array is sorted after three passes.
Example 2
Input: nums = [4, 4, -7, 4]
[-7,4,4,4]Explanation: Two equal neighbours are never swapped. The −7 moves one place left in each pass until it reaches the front.
Example 3
Input: nums = [10, 20, 30]
[10,20,30]Explanation: The array is already in order. The first pass makes no swaps, so one pass is enough.
Check your understanding
Work out the answer for this input before you write any code.
Constraints
1 ≤ nums.length ≤ 2000-109 ≤ nums[i] ≤ 109
Clarifying questions
What you would ask an interviewer before writing any code.