Bubble sort

See Wikipedia’s article on Bubble sort for explanation. Following is my implementation in Python of both the classical version and an optimised variant.


def bubble_sort(A):
    n = len(A)
    for i in range(0, n):
        for j in range(1, n):
            if A[j - 1] > A[j]:  # swap numbers
                # Python "magick" to allow for assignment without tmp variable
                # A[j], A[j - 1] = A[j - 1], A[j]
                
                # Swapping list elements without Python magic
                temp = A[j]
                A[j] = A[j - 1]
                A[j - 1] = temp

    return A

def bubble_sort_optimised(A):
    n = len(A)
    for i in range(0, n):
        for j in range(1, n):
            if A[j - 1] > A[j]:  # swap numbers
                A[j], A[j - 1] = A[j - 1], A[j]

        n -= 1

    return A
Complexity analysis Link to heading
  • Time: $ O(n^2) $ in the worst case scenario.


Share on:
LinkedIn