How Many Bubble Sort Passes?

Bubble sort walks along the list comparing neighbours. Whenever the left one is bigger than the right one it swaps them. One walk from start to end is a pass. It stops after the first pass in which nothing was swapped.

passes = 0
while True:
    passes += 1
    swapped = False
    for i in range(len(a) - 1):
        if a[i] > a[i + 1]:
            a[i], a[i + 1] = a[i + 1], a[i]
            swapped = True
    if not swapped:
        break

Return the final value of passes, counting the last pass that swapped nothing. A list that is already sorted, and a list with fewer than two items, takes 1 pass.

Examples

Example 1

Input:

bubble_sort_passes([3, 2, 1])

Output:

3

Pass 1 gives [2, 1, 3], pass 2 gives [1, 2, 3], pass 3 swaps nothing: 3 passes.

Example 2

Input:

bubble_sort_passes([1, 2, 3])

Output:

1

No swaps in the first pass, so it stops after 1.

Constraints

• 0 <= len(nums) <= 1500
• -10**9 <= nums[i] <= 10**9