My improved version of bubble sort algorithm

Posted on Mon 16 October 2017 in Software Engineering

This document is not about explaining the bubble sort algorithm as it already exists a good literature out there about it, and it is a classic algorithm studied and known by all CS students all over the world.

There are, obviously, two improved versions of bubble sort algorithm; and thanks to a question asked the Code Review website regarding the first one of them which is:

procedure bubbleSort( A : list of sortable items )
    n = length(A)
    repeat
        swapped = false
        for i = 1 to n-1 inclusive do
            if A[i-1] > A[i] then
                swap(A[i-1], A[i])
                swapped = true
            end if
        end for
        n = n - 1
    until not swapped
end procedure

Here is its Python implementation (as provided by the OP):

def bubble_sort(array):
    n = len(array)
    swapped = True
    while swapped:
        swapped = False
        for i in range(n - 1):
            if array[i] > array[i + 1]:
                array[i], array[i + 1] = array[i + 1], array[i]
                swapped = True
        n -= 1
    return array

My version removes away a good bunch of the algorithm’s complexity by getting totally rid of the swapped variable flag above and all the instructions inherent to it:

def bubble_sort(array):
    n = len(array)
    while n:
        for i in range(n - 1):
            if array[i] > array[i + 1]:
                array[i], array[i + 1] = array[i + 1], array[i]
        n -= 1
    return array

The lengthier the input array is, the more tangible the complexity my version gets rid of becomes important. Well ... maybe this deserve to be mentioned in the literature too :)