Python : Bubble Sort - Step-by-Step Explanation with Code

on

 



Bubble Sort: Step-by-Step Explanation with Code

Sorting is one of the most fundamental concepts in programming, and Bubble Sort is often the first algorithm beginners learn. Though simple, it lays the foundation for understanding more efficient sorting algorithms later.

Let’s explore what Bubble Sort is, how it works, and how to implement it in Python.

What is Bubble Sort?

Bubble Sort is a simple sorting algorithm that repeatedly compares adjacent elements in a list and swaps them if they are in the wrong order.

The largest element “bubbles up” to the end of the list with each pass — hence the name Bubble Sort.

Step-by-Step Walkthrough

Let’s sort the array:
[5, 1, 4, 2, 8]

Pass 1:

  • Compare 5 & 1 → Swap → [1, 5, 4, 2, 8]

  • Compare 5 & 4 → Swap → [1, 4, 5, 2, 8]

  • Compare 5 & 2 → Swap → [1, 4, 2, 5, 8]

  • Compare 5 & 8 → No swap

After Pass 1: [1, 4, 2, 5, 8]

Pass 2:

  • Compare 1 & 4 → No swap

  • Compare 4 & 2 → Swap → [1, 2, 4, 5, 8]

  • Compare 4 & 5 → No swap

  • Compare 5 & 8 → No swap

 After Pass 2: [1, 2, 4, 5, 8]

Pass 3:
No swaps → The list is now sorted.

Final Output: [1, 2, 4, 5, 8]

Python Code for Bubble Sort

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        swapped = False
        for j in range(0, n - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True
        if not swapped:
            break  # Optimization: stop if no swaps occurred

arr = [5, 1, 4, 2, 8]
bubble_sort(arr)
print("Sorted array:", arr)

Output:

Sorted array: [1, 2, 4, 5, 8]

Time & Space Complexity

Case Time Complexity
Best Case (Already Sorted) O(n)
Average Case O(n²)
Worst Case O(n²)

Space Complexity: O(1) (in-place sorting)

 Features of Bubble Sort

- Easy to understand and implement
- Works well for small datasets
- Not efficient for large lists
- Can detect if a list is already sorted (optimized version)

Real-Life Analogy/Example

Imagine sorting a line of students by height. You repeatedly compare two students standing next to each other and swap them if they are out of order. After each round, the tallest student moves to the end of the line — just like “bubbling up” in Bubble Sort!

Summary

Feature Description
Type Comparison-based
Method Repeated swapping of adjacent elements
Stable Yes
In-place Yes
Efficiency Poor for large datasets
Best Use Case Teaching and small data sorting

Conclusion

Bubble Sort is not the fastest algorithm, but it’s a great starting point to understand how sorting works. Once you master Bubble Sort, you’ll find it easier to grasp advanced algorithms like Merge Sort and Quick Sort.



Comments

Post a Comment