Bubble Sort

bubble_sort(x)

Bubble sort repeatedly compares adjacent elements and swaps those that are wrongly ordered. This process is repeated till the list is fully sorted. It has an average time complexity of Θ(n^2) due to the nesting of its two loops. Time complexity for the worst case, when the list is sorted in reverse order, is O(n^2). Time complexity for the best case, when the list is already sorted in the correct order, is Ω(n).

bubble_sort([4, 2, 3, 1, 0, 5]) [0, 1, 2, 3, 4, 5]

Parameters:

Name	Type	Description	Default
x	List	list to be sorted	required

Returns:

Type	Description
List	new sorted list

Source code in sorting_algorithms/bubble_sort.py

def bubble_sort(x: List) -> List:
    """Bubble sort repeatedly compares adjacent elements and swaps those that are wrongly ordered. This process is
    repeated till the list is fully sorted. It has an average time complexity of Θ(n^2) due to the nesting of its two
    loops. Time complexity for the worst case, when the list is sorted in reverse order, is O(n^2). Time complexity for
    the best case, when the list is already sorted in the correct order, is Ω(n).

    >>> bubble_sort([4, 2, 3, 1, 0, 5])
    [0, 1, 2, 3, 4, 5]

    :param x: list to be sorted
    :return: new sorted list
    """
    a_list = copy.deepcopy(x)  # To avoid modifying the original list
    length = len(a_list)

    for _ in range(length - 1):
        swapped = False

        for current_idx in range(length - 1):
            next_idx = current_idx + 1

            if a_list[current_idx] > a_list[next_idx]:
                swapped = True
                a_list[current_idx], a_list[next_idx] = (
                    a_list[next_idx],
                    a_list[current_idx],
                )

        # If no swap takes place, it means that the list is fully sorted
        # The remaining loops can therefore be safely ignored
        if not swapped:
            break

    return a_list