Bubble Sort in Python

Bubble Sort is one of the easiest sorting algorithms. It is usually taught to introduce the concept of sorting. Here’s a step-by-step explanation of how it works, along with an example in Python:

Concept of Bubble Sort

• This repeatedly steps through the list, comparing adjacent elements and swapping them if they are in the wrong order.
• Repeat the process until the list is sorted.
• Larger elements “bubbles up” to the top of the list in each go, and vice versa, is smaller.

Steps of Bubble Sort

1. Starting from the beginning of the list
2. Compare the first two elements:
   • If the first element is greater than the second, swap them
3. Move to the next pair of elements and repeat the comparison and swapping if needed.
4. Continue until the end of the list
5. After each pass, the largest element will have settled at its correct position (at the end of the unsorted portion).
6. Repeat for the remaining unsorted part of the list until there is no further swap required.

Efficiency

• Time Complexity:
  • Best Case (Already Sorted): O(n)
  • Worst Case (Reverse Order): O(n^2)
  • Average Case:mO(n^2)
• Space Complexity: O(1) (in-place sorting, no extra memory needed).

Bubble Sort is inefficient for large datasets but is easy to implement and understand.

Python Implementation

Here’s how Bubble Sort can be implemented in Python:

def bubble_sort(arr):
    n = len(arr)
    # Outer loop for the number of passes
    for i in range(n):
        # Track if any swaps happen during this pass
        swapped = False
        # Inner loop for comparing adjacent elements
        for j in range(0, n - i - 1):
            if arr[j] > arr[j + 1]:
                # Swap if the elements are in the wrong order
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True
        # If no swaps were made, the array is already sorted
        if not swapped:
            break

# Example usage
numbers = [64, 34, 25, 12, 22, 11, 90]
print("Original list:", numbers)

bubble_sort(numbers)
print("Sorted list:", numbers)

Explanation of the Code

1. Outer Loop:

• Determines the number of passes required (up to n−1).
• For each pass “bubbles up” the largest unsorted element to its position.

2. Inner Loop:

• Compares two adjacent elements and swaps them when they are in the wrong order.
• Eliminates one end of the sorted range after each pass because that end is already sorted.

3. Optimization with the Swapped Flag:

• If no swaps are done in a pass, the list is already sorted and the algorithm can stop here.

Example Walkthrough

Sort the list: [5, 3, 8, 6].

• Pass 1:
  • Compare 5 and 3 → Swap → [3, 5, 8, 6]
  • Compare 5 and 8 → No Swap → [3, 5, 8, 6]
  • Compare 8 and 6 → Swap → [3, 5, 6, 8]
• Pass 2:
  • Compare 3 and 5 → No Swap → [3, 5, 6, 8]
  • Compare 5 and 6 → No Swap → [3, 5, 6, 8]

Since no swaps happen in the pass 2, the algorithm also terminates early.

Key Notes

• Advantages: Easy to understand and implement.
• Disadvantages: Inefficient for large datasets.
• Best Use Case: Small datasets or when simplicity is prioritized over performance.