Given a list of integers arr, implement the bubble sort algorithm to sort the list in non-decreasing order. Bubble sort works by repeatedly swapping adjacent elements if they are in the wrong order.
Example 1:
Input: arr = [5, 2, 9, 1, 5, 6]
Output: [1, 2, 5, 5, 6, 9]
Example 2:
Input: arr = [3, 0, 2, 5, -1, 4, 1]
Output: [-1, 0, 1, 2, 3, 4, 5]
1 <= arr.length <= 1000-10^3 <= arr[i] <= 10^3arr = [5, 2, 9, 1, 5, 6]Output[1, 2, 5, 5, 6, 9]WhyAfter sorting, the smallest element (1) is at the start, and the largest (9) is at the end.arr = [3, 0, 2, 5, -1, 4, 1]Output[-1, 0, 1, 2, 3, 4, 5]WhyThe elements are rearranged in ascending order from the smallest (-1) to the largest (5).1 <= arr.length <= 1000-10^3 <= arr[i] <= 10^3def bubble_sort(arr: list[int]) -> list[int]:
