Bubble Sort Algorithm in Python

The bubble sort is simplest of all sorting routines. Sorting in this context refers to arranging a list of data(array in other languages) in some order say ascending and descending for numbers and alphabetical order for strings.

To begin with, imagine that we have an list of numbers that we wish to sort in ascending order. The bubble sort algorithm starts by comparing the first two elements in the list and swaps them if they are not in ascending order for our example. You then continue comparing each subsequent pair in the list until we reach the last entry. At this stage, the last entry is the largest element in the array.

The process is repeated all over until the list is fully sorted.

Here’s the Python code:


def bubble_sort(lst): 
    nums = list(lst)
    for i in range(len(lst)):
        for j in range(i+1, len(lst)):
            if lst[j] < lst[i]:
                lst[j], lst[i] = lst[i], lst[j]
    return lst

Note that during each iteration the largest number in the iteration moves or "bubbles" to the end of the list. This is what gives the algorithm its name.

Bubble sort is slow algorithm. To explain this let us look at the time complexity.

Suppose that the unsorted list has n elements. We perform n-1 comparisons in the first iteration. In the second iteration we perform n-2 comparisons and so on.Therefore the number of steps involves would be:

(n-1)+ (n-2)+ ... + 1

This is an arithmetic progression series that sums to:
n^2 - n/2 steps

For large values of n, we can ignore the (n/2) portion of the equation as n^2 is the dominant part of the equation.
Therefore the order of complexity for bubble sort algorithm as expressed in big o notation as o(n^2)