Bubble Sort

Lab Python Intermediate 20 points

Implement bubble sort. Print the list after every pass that swapped something, then print the number of swaps.

Input

One line of integers.

Output

The list after each pass, then the swap count.

Example

Input

5 1 4 2 8

Output

1 4 2 5 8
1 2 4 5 8
4

Sample input available Sample output available

Editor

Python

Hints

Each pass bubbles the largest remaining value to the end.

Stop early when a pass makes no swaps.

Solution explanation

Bubble sort is O(n²) - fine for learning, too slow for big data. Python's sorted uses Timsort (O(n log n)).

Show solution

nums = list(map(int, input().split()))
swaps = 0
for end in range(len(nums) - 1, 0, -1):
    swapped = False
    for i in range(end):
        if nums[i] > nums[i + 1]:
            nums[i], nums[i + 1] = nums[i + 1], nums[i]
            swaps += 1
            swapped = True
    if not swapped:
        break
    print(*nums)
print(swaps)

Output

Answer