Sorting — Bubble Sort

Python Data Structures and Algorithms — Day 3

Bubble Sort is a simple sorting algorithm that repeatedly steps through the list of elements to be sorted, compares each pair of adjacent items, and swaps them if they are in the wrong order.

The pass through the list is repeated until no swaps are needed, indicating that the list is sorted. The algorithm gets its name because smaller elements “bubble” to the top of the list during each pass.

Basic explanation of the Bubble Sort algorithm

Comparison and Swapping

• The algorithm starts by comparing the first two elements of the list.
• If the first element is greater than the second element, they are swapped.
• If the first element is smaller or equal to the second element, no swap is performed.

Iteration

• The algorithm then moves to the next pair of elements and repeats the comparison and swapping process.
• This process is repeated for each pair of adjacent elements in the list.

Passes

• After the first pass, the largest element has moved to its correct position at the end of the list.
• The algorithm then repeats the process for the remaining elements (excluding the last one) in the second pass.
• The process continues until no more swaps are needed in a pass, indicating that the list is sorted.

Optimization

• It’s important to note that the algorithm can be optimized by stopping the algorithm if no swaps are made during a pass, as this indicates that the list is already sorted.

procedure bubbleSort(arr: array of comparable elements)
    n = length(arr)
    repeat
        swapped = false
        for i from 1 to n-1
            if arr[i-1] > arr[i]
                swap(arr[i-1], arr[i])
                swapped = true
        n = n - 1
    until not swapped
end procedure

This pseudocode outlines the basic steps of the Bubble Sort algorithm. It uses a flag swapped to track whether any swaps were made during a pass. The algorithm repeats the process of comparing and swapping until no more swaps are needed, indicating that the array is sorted. The outer loop (repeat...until) is used to iterate through the array until it is completely sorted.

Python Code for Bubble Sort

def bubble_sort(arr):
    n = len(arr) # length of the array
    
    # Traverse through all array elements
    for i in range(n):
        # Last i elements are already in place, so we don't need to check them
        for j in range(0, n-i-1):
            
            # Swap if the element found is greater than the next element
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]

# Example usage:
my_list = [64, 34, 25, 12, 22, 11, 90]
bubble_sort(my_list)

print("Sorted array:", my_list)

Here’s the optimized bubble sort where we reduce the number of steps required for the algorithm to terminate.

def optimized_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 no swaps were made during the inner loop, the array is already sorted
        if not swapped:
            break

# Example usage:
my_list = [64, 34, 25, 12, 22, 11, 90]
optimized_bubble_sort(my_list)

print("Sorted array:", my_list)

Analysis of Bubble Sort Algorithm

Time Complexity

The time complexity of the optimized Bubble Sort algorithm in the worst case is O(n²) which is the same as that of the standard bubble sort. This is because, in the worst case, the algorithm performs comparisons and swaps for each pair of elements in the list.

The optimization primarily impacts the best-case scenario and some average cases, where the algorithm can terminate early if the array is already sorted or nearly sorted. In the best-case scenario, where the array is already sorted, the time complexity can be reduced to O(n) because the algorithm breaks out of the outer loop as soon as it detects that no swaps were made in a pass.

So, while the optimization doesn’t change the worst-case time complexity, it can make the algorithm more efficient in certain situations, particularly when dealing with partially sorted data.

Space Complexity

The space complexity of Bubble Sort is O(1), which means that the algorithm uses a constant amount of additional space regardless of the size of the input list. Bubble Sort performs sorting in place and doesn’t require any additional data structures proportional to the input size.

Stability

Bubble Sort is a stable sorting algorithm. Stability in sorting means that the relative order of equal elements remains unchanged after sorting. In Bubble Sort, if two elements have equal values and the algorithm decides not to swap them because they are in the correct order (i.e., not violating the stability), their relative order will be preserved.

Adaptiveness

Bubble Sort is considered adaptive. An algorithm is said to be adaptive if it becomes more efficient when applied to a partially sorted input.

In the case of Bubble Sort, if the list is nearly sorted, the algorithm will require fewer passes to complete the sorting process. This adaptability is due to the fact that Bubble Sort stops early if no swaps are needed during a pass, making it more efficient in certain situations.

Conclusion

Bubble Sort is easy to implement and understand, making it a good educational tool and a simple solution for small datasets or situations where its limitations are not critical.

Despite its simplicity and stability, Bubble Sort is not commonly used in practice for large datasets due to its relatively poor performance. More efficient sorting algorithms, such as QuickSort or MergeSort, are often preferred in real-world applications.