# A slightly improved version of bubble sort algorithm

My wicked brain gave birth to an improved version of the classic bubble sort algorithm. Here it is.

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 :)