Bubble Sort Program in Python

Bubble Sort

Bubble Sort is a sorting algorithm that sorts the given list of items in a specific 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, similar to the behavior of bubbles in water.

Bubble Sort should be considered for educational purposes or as a starting point for learning Sorting Algorithms. However, for practical uses, more efficient algorithms such as Merge Sort should be used.

Bubble Sort Algorithm

The algorithm for Bubble Sort is as follows:

  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 position).
  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 the Bubble Sort algorithm. By default, the bubble_sort() function in this program sorts the list in ascending order. To sort in descending order, you just need to reverse the list after sorting.

Python Program

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)

Explanation:

  1. The outer loop runs through the entire list and progressively moves towards the start of the list after each pass.
  2. The inner loop compares adjacent elements and swaps them if the left element is greater than the right element.
  3. This process is repeated until no more swaps are required, indicating the list is sorted.

Output

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

We can optimize the program by checking if any swaps were made during a pass. If no swaps occur, it means the list is already sorted, and we can stop the algorithm early. This reduces unnecessary comparisons.

Improved Python 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)

Explanation:

  1. The no_swap variable is used to detect if any swaps occurred during the pass. If no swaps happen, the algorithm terminates early, saving time on unnecessary passes.
  2. If any elements are swapped, no_swap is set to False, indicating the need for another pass.

Output

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

Additional Example: Sorting a Larger List

Here's an example of sorting a larger list with Bubble Sort. This will demonstrate how the algorithm handles more elements:

Python Program

alist = [45, 23, 89, 12, 65, 38, 97, 4, 56, 19]
bubble_sort(alist)
print('Sorted List\n', alist)

Output

Sorted List
 [4, 12, 19, 23, 38, 45, 56, 65, 89, 97]

Summary

In this tutorial of Python Algorithms, we have learned how to implement the Bubble Sort algorithm in Python. Bubble Sort is simple but inefficient for large datasets. We also discussed optimizations to improve its performance, such as checking for no swaps to terminate early.

Python Libraries