def bubble_sort(arr):
    """
    Exchange sort (bubble sort)
    1. Take the first element each time and compare it with the next element. If the former is larger than the latter,
    switch positions and compare with the latter. If the latter bit is greater, it is not exchanged.
    Then the next bit is compared with the next bit until the last indexed element. At this time,
    the last indexed element is the largest, and it is also the element that will never be moved after sorting.
    That is, L[n-i:n] is arranged so as not to move.
    2. The above rule loops for n-1 rounds, then the sorting is complete.

    Average Time Complexity: O(n**2)
    Space Complexity: O(1)
    stability: Yes
    Best Time Complexity: O(n)
    Worst Time Complexity: O(n**2)
    :param arr:
    :return:
    """
    for i in range(len(arr)-1):
        for j in range(len(arr)-1-i):
            if arr[j] > arr[j+1]:
                arr[j],arr[j+1] = arr[j+1],arr[j]
    return arr