Bubble Sort Program in Python

What is Bubble Sort?
Bubble Sort in Python is a simple sorting algorithm that repeatedly swaps adjacent elements if they are in the wrong order, gradually moving larger elements towards the end of the list.

Write a Python program to implement bubble sort.

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

In the code above, the bubble_sort function takes a list (lst) as input and performs the Bubble Sort algorithm. It iterates through the list multiple times, comparing adjacent elements and swapping them if they are in the wrong order. This process is repeated until the list is fully sorted.

Here’s an example of the Bubble Sort algorithm applied to the list “4 2 38 10 5“:

• Step 1: Start with the given list [4, 2, 38, 10, 5].
• Step 2: Compare the first pair of adjacent elements (4 and 2). Since 4 is greater than 2, swap them.
  List becomes [2, 4, 38, 10, 5].
• Step 3: Continue comparing adjacent elements and swapping if necessary.
  [2, 4, 10, 38, 5]
  [2, 4, 10, 5, 38]
• Step 4: Repeat the process until the list is fully sorted.
  [2, 4, 10, 5, 38]
  [2, 4, 5, 10, 38]
  [2, 4, 5, 10, 38] (sorted)

The final sorted list is [2, 4, 5, 10, 38].

Here is the source code of a Python program to implement bubble sort. The program output is shown below.

def bubble_sort(alist):
    for i in range(len(alist) - 1, 0, -1):
        no_swap = True
        for j in range(0, i):
            if alist[j + 1] < alist[j]:
                alist[j], alist[j + 1] = alist[j + 1], alist[j]
                no_swap = False
        if no_swap:
            return
 
 
alist = input('Enter the list of numbers: ').split()
alist = [int(x) for x in alist]
bubble_sort(alist)
print('Sorted list: ', end='')
print(alist)

1. Define the bubble_sort function that takes a list (alist) as input.
2. Iterate through the list in reverse order, starting from the last index (len(alist) – 1) and ending at the second index (0) using a step size of -1.
3. Set a flag no_swap to True, indicating no swaps have occurred yet.
4. Enter a nested loop that iterates from the first index (0) to the current outer loop index (i).
5. Compare adjacent elements and swap them if the element on the right is smaller than the element on the left.
6. Set the no_swap flag to False if a swap occurs, indicating that the list is not yet fully sorted.
7. Check if the no_swap flag is still True after the inner loop completes. If it is, return from the function as the list is already sorted.
8. Outside the function, prompt the user to enter a list of numbers, which are stored as a string and split into individual elements.
9. Convert the elements from strings to integers using a list comprehension.
10. Call the bubble_sort function to sort the list using the Bubble Sort algorithm.
11. Print the sorted list.

Time Complexity of Bubble Sort Program:

• Best case: O(n)
• Average case: O(n²)
• Worst case: O(n²)

The time complexity of the program is O(n²) in both average and worst cases, where n is the number of elements in the input list. The best case time complexity is O(n) when the list is already sorted.

Space Complexity: O(1)
The space complexity of the program is O(1) since it uses a constant amount of additional space.

Testcase 1: In this case, we are entering the numbers “4, 2, 38, 10, and 5” as input to sort them using bubble sort in ascending order.

Enter the list of numbers: 4 2 38 10 5
Sorted list: [2, 4, 5, 10, 38]

Testcase 2: In this case, we are entering the numbers “5, 4, 3, 2, and 1” as input to sort them using bubble sort in ascending order.

Enter the list of numbers: 5 4 3 2 1
Sorted list: [1, 2, 3, 4, 5]

Testcase 3: In this case, we are entering the numbers “7, 3, 1, -5, 2, and 10” as input to sort them using bubble sort in ascending order.

Enter the list of numbers: 7 3 1 -5 2 10
Sorted list: [-5, 1, 2, 3, 7, 10]

To practice programs on every topic in Python, please visit “Programming Examples in Python”.