Bubble Sort

Bubble sort is one of the simplest sorting algorithms. Its name comes from the way smaller elements "bubble" up to the start of the list during the sorting process.

Definition

Bubble sort is a basic sorting method that repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. By repeatedly doing this, the smaller values gradually rise to the beginning of the list, much like bubbles rising in water.

How It Works

The algorithm works by iterating over the list and comparing each pair of adjacent elements. If the element on the left is greater than the element on the right (assuming we are sorting in non-decreasing order), the two elements are swapped. This process is repeated until no more swaps are needed, which means the list is sorted.

After each complete pass through the list, the largest unsorted element "bubbles" up to its correct position at the end of the list. This means after $i$ passes, the last $i$ elements are in their final sorted positions. In the worst-case scenario, the algorithm needs to make $n-1$ passes through an array of $n$ elements.

Properties

Stability

Bubble sort is a stable sorting algorithm. This means that if two elements have equal values, their original order will be preserved in the sorted list.

Time Complexity

In the best-case scenario (when the list is already sorted), bubble sort only requires one pass through the array with no swaps, yielding a time complexity of $O(n)$ .
In the worst-case scenario, the algorithm performs $\frac{(n-1)n}{2}$ swaps, resulting in a time complexity of $O(n^2)$ .
On average, the time complexity of bubble sort is also $O(n^2)$ .

Pseudocode

Below is a step-by-step pseudocode representation of bubble sort:

\begin{array}{ll} 1 & \textbf{Input: An array } A \text{ with } n \text{ elements.}\\[6pt] 2 & \textbf{Output: Array } A \text{ sorted in non-decreasing order, ensuring stability.}\\[6pt] 3 & \textbf{Method:}\\[6pt] 4 & \quad flag \gets \text{True}\\[6pt] 5 & \quad \textbf{while } flag \text{ is True}\\[6pt] 6 & \quad\quad flag \gets \text{False}\\[6pt] 7 & \quad\quad \textbf{for } i \gets 1 \textbf{ to } n-1\\[6pt] 8 & \quad\quad\quad \textbf{if } A[i] > A[i+1] \text{ then}\\[6pt] 9 & \quad\quad\quad\quad flag \gets \text{True}\\[6pt] 10 & \quad\quad\quad\quad \text{Swap } A[i] \text{ and } A[i+1] \end{array}

Python Implementation

Here is a simple implementation of bubble sort in Python:

def bubble_sort(arr):
    n = len(arr)
    flag = True
    while flag:
        flag = False
        for i in range(n - 1):
            if arr[i] > arr[i + 1]:
                flag = True
                arr[i], arr[i + 1] = arr[i + 1], arr[i]
    return arr
 
# Example usage:
if __name__ == "__main__":
    sample_array = [64, 34, 25, 12, 22, 11, 90]
    sorted_array = bubble_sort(sample_array)
    print("Sorted Array:", sorted_array)

This implementation iterates through the list repeatedly and swaps adjacent elements if they are in the wrong order until no more swaps occur, ensuring the list is fully sorted.

Bubble sort is ideal for beginners due to its simple structure and ease of understanding, even though it may not be the most efficient choice for large datasets.

Introduction Bucket Sort