Bubble Sort

Bubble sort is a simple sorting algorithm that repeatedly steps through the list, compares adjacent elements and swaps them if they are in the wrong order. The pass through the list is repeated until the list is sorted.

Algorithm Overview

The algorithm works by repeatedly comparing adjacent elements and swapping them if they are in the wrong order. After each complete pass through the array, the largest unsorted element "bubbles up" to its correct position.

Key Features

Simple Implementation: Easy to understand and implement
Stable: Maintains relative order of equal elements
In-Place: Sorts the array without using extra space
Adaptive: Can detect if the list is already sorted (optimized version)
Educational Value: Great for learning sorting concepts

Time and Space Complexity

Time Complexity:
Best Case: O(n) - when array is already sorted (with optimization)
Average Case: O(n²)
Worst Case: O(n²) - when array is reverse sorted
Space Complexity: O(1) - sorts in place

Algorithm Steps

Compare adjacent elements starting from the first pair
Swap them if they are in wrong order (left > right for ascending)
Continue comparing all adjacent pairs in the current pass
Repeat passes until no swaps are needed
Optimization: Stop early if no swaps occur in a pass

Usage Examples

Basic Usage

from algo.algorithms.sorting.bubble_sort import bubble_sort

# Sort integers
numbers = [64, 34, 25, 12, 22, 11, 90]
sorted_numbers = bubble_sort(numbers)
print(sorted_numbers)  # [11, 12, 22, 25, 34, 64, 90]

# Sort strings
words = ['banana', 'apple', 'cherry']
sorted_words = bubble_sort(words)
print(sorted_words)  # ['apple', 'banana', 'cherry']

# Empty array
result = bubble_sort([])
print(result)  # []

Educational/Debugging

from algo.algorithms.sorting.bubble_sort import bubble_sort_verbose

# See step-by-step process
bubble_sort_verbose([64, 34, 25, 12])

Output:

Starting bubble sort on: [64, 34, 25, 12]

Pass 1:
  Comparing 64 and 34 -> Swapped! Array: [34, 64, 25, 12]
  Comparing 64 and 25 -> Swapped! Array: [34, 25, 64, 12]
  Comparing 64 and 12 -> Swapped! Array: [34, 25, 12, 64]
  End of pass 1: [34, 25, 12, 64]

Pass 2:
  Comparing 34 and 25 -> Swapped! Array: [25, 34, 12, 64]
  Comparing 34 and 12 -> Swapped! Array: [25, 12, 34, 64]
  End of pass 2: [25, 12, 34, 64]

Pass 3:
  Comparing 25 and 12 -> Swapped! Array: [12, 25, 34, 64]
  End of pass 3: [12, 25, 34, 64]

Final sorted array: [12, 25, 34, 64]

Edge Cases Handled

# Empty array
result = bubble_sort([])  # Returns []

# Single element
result = bubble_sort([42])  # Returns [42]

# Already sorted
result = bubble_sort([1, 2, 3, 4])  # Completes in O(n) with optimization

# Reverse sorted (worst case)
result = bubble_sort([4, 3, 2, 1])  # Returns [1, 2, 3, 4]

# Duplicates
result = bubble_sort([3, 1, 3, 1])  # Returns [1, 1, 3, 3]

API Reference

Bubble Sort Algorithm Implementation

Bubble sort is a simple sorting algorithm that repeatedly steps through the list, compares adjacent elements and swaps them if they are in the wrong order. The pass through the list is repeated until the list is sorted.

Time Complexity: O(n²) in worst and average case, O(n) in best case

Space Complexity: O(1) - sorts in place

Stability: Stable (maintains relative order of equal elements)

`bubble_sort(arr)`

Sort an array using the bubble sort algorithm.

The algorithm works by repeatedly comparing adjacent elements and swapping them if they are in the wrong order. After each complete pass through the array, the largest unsorted element "bubbles up" to its correct position.

Parameters:

Name	Type	Description	Default
`arr`	`List[T]`	List of comparable elements to sort	required

Returns:

Type	Description
`List[T]`	The sorted list (sorted in-place, but also returned for convenience)

Examples:

>>> bubble_sort([64, 34, 25, 12, 22, 11, 90])
[11, 12, 22, 25, 34, 64, 90]

>>> bubble_sort(['banana', 'apple', 'cherry'])
['apple', 'banana', 'cherry']

>>> bubble_sort([])
[]

`bubble_sort_verbose(arr)`

Bubble sort with detailed step-by-step output for educational purposes.

This version prints each step of the sorting process to help understand how the algorithm works.

Parameters:

Name	Type	Description	Default
`arr`	`List[T]`	List of comparable elements to sort	required

Returns:

Type	Description
`List[T]`	The sorted list