Python - Bubble Sort Algorithm Implementation

Bubble sort algorithm - In this article, we will learn about one of the sorting algorithms - Bubble sort. Time complexity of this algorithm is O(n^2) and space complexity being O(1).

Bubble Sort Algorithm

for i = 0 to [length(array) - 1]
begin
    # To keep track of whether a swap has happened
    flag = 0

    # Last 'i' elements will always be sorted
    for j = 0 to [length(array) - i - 1]
    begin
        
        # Check if array[j] > array[j+1], Swap if True
        if array[j] > array[j+1]
        begin
            swap array[j] and array[j+1]
            flag = 1
        endif
    endfor

    if flag == 0
    begin
        break
    endif

endfor

return array

Example

Consider the following list-

Here, length of the array is 8, hence there outer loop, which we will refer to as a pass, will be executed 8 times, while inner loop will be executed (8 - 0 - 1) times. Lets see the first pass.

Pass 1-1:

i = 0, j = 0
array[0] = 5, array[0+1] = 3
array[0] > array[1]
Result - 5 and 3 will be swapped.

Pass 1-2:

i = 0, j = 1
array[1] = 5, array[1+1] = 7
array[1] < array[2]
Result - Nothing happens

Pass 1-3:

i = 0, j = 2
array[2] = 7, array[2+1] = 1
array[2] > array[3]
Result - 7 and 1 will be swapped

Pass 1-4:

i = 0, j = 3
array[3] = 7, array[3+1] = 4
array[3] > array[4]
Result - 7 and 4 will be swapped

 

Pass 1-5:

i = 0, j = 4
array[4] = 7, array[4+1] = 8
array[4] < array[5]
Result - Nothing happens

Pass 1-6:

i = 0, j = 5
array[5] = 8, array[5+1] = 2
array[5] > array[6]
Result - 8 and 2 will be swapped

Pass 1-7:

i = 0, j = 6
array[6] = 8, array[6+1] = 6
array[7] > array[7]
Result - 8 and 6 will be swapped

Observation - After once complete pass, it can be observed that, the largest element in the array is bubbled up to the last position in the array. In another words, after one pass, one element in the array is sorted. Also, if no swap happens, it can be concluded that the array is sorted and we can break out of the loop. To keep track of this, we have introduced variable flag in the algorithm.

Similarly, after subsequent passes, array will look like -

After the 5th pass, there will be no swapping. Hence there is no need for more iterations and the process can be stopped.

Python Implementation:

def bubble_sort(array):
    n = len(array)
    
    for i in range(n):
        flag = 0
        
        for j in range(n-i-1):
            if array[j] > array[j+1]:
                array[j], array[j+1] = array[j+1], array[j]
                flag = 1
                
        if flag == 0:
            break

my_array = [5, 3, 7, 1, 4, 8, 2, 6]
bubble_sort(my_array)
print my_array

Output:

[1, 2, 3, 4, 5, 6, 7, 8]