Python Bubble Sort Program

Bubble Sort

Bubble Sort is a sorting algorithm which sorts the given list of items in an order.

Bubble sort repeatedly steps through the given list, compares adjacent elements, and swaps them if they are in the incorrect order. The pass through the list is repeated until the list is completely sorted.

Bubble Sort gets its name because smaller elements “bubble” to the top of the list while larger elements “sink” to the bottom. Just like a bubble in water.

Bubble Sort should be considered for only educational purposes or to get started with Sorting Algorithms. But, when it comes to practical purposes, use better performing sorting algorithms like Merge Sort.

Bubble Sort Algorithm

The algorithm for Bubble sort is given below.

1. Start from the beginning of the list.
2. Compare the current element with the next element.
3. If the current element is greater than the next element, swap them.
4. Move to the next element and repeat the comparison and swap.
5. Continue this process for all elements in the list.
6. After the first pass, the largest element will have “bubbled up” to the last position.
7. Repeat the process for the remaining unsorted portion of the list (excluding the last element that’s already in its correct place).
8. Continue these passes until no more swaps are needed, indicating that the list is fully sorted.

Python Program for Bubble Sort

In the following example, we have implemented Bubble Sort Algorithm. Also, by default, the bubble_sort() function in the following program sorts the list in ascending order. To get the descending order, all you have to do is just reverse the list.

def bubble_sort(nlist):
    for i in range(len(nlist) - 1, 0, -1):
        for j in range(0, i):
            if nlist[j + 1] < nlist[j]:
                nlist[j], nlist[j + 1] = nlist[j + 1], nlist[j]

# Input list
alist = [1, 74, 96, 5, 42, 63]
print('Input List\n', alist)

# Sort list
bubble_sort(alist)
print('Sorted List\n', alist)

Output

Input List
 [1, 74, 96, 5, 42, 63]
Sorted List
 [1, 5, 42, 63, 74, 96]

We can improve the For loop, by checking if there is any swap operation done in a pass. If no swap operation is performed in a pass, then the elements are already in their ordered position, and no more passes are required.

To detect if there is no swap, we shall use the variable no_swap, as shown in the following program.

def bubble_sort(nlist):
    for i in range(len(nlist) - 1, 0, -1):
        no_swap = True
        for j in range(0, i):
            if nlist[j + 1] < nlist[j]:
                nlist[j], nlist[j + 1] = nlist[j + 1], nlist[j]
                no_swap = False
        if no_swap:
            return

# Input list
alist = [1, 74, 96, 5, 42, 63]
print('Input List\n', alist)

# Sort list
bubble_sort(alist)
print('Sorted List\n', alist)

Output

Input List
 [1, 74, 96, 5, 42, 63]
Sorted List
 [1, 5, 42, 63, 74, 96]

Summary

In this tutorial of Python Algorithms, we learned how to implement Bubble Sort algorithm in Python.