How the Bubble Sort Algorithm Works

Bubble Sort Algorithm Explained

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.

How it works:

1. Iteration: Start with the first element in the list.
2. Comparison: Compare the current element with the next element.
3. Swap: If the current element is greater than the next element, swap them.
4. Repeat: Repeat steps 2 and 3 for all remaining elements in the list.
5. Next Iteration: Repeat steps 1 to 4 for the entire list until no swaps are made in an iteration.

Example:

Let's sort the array [5, 1, 4, 2, 8].

Iteration 1:

• Compare 5 and 1: Swap (1, 5, 4, 2, 8)
• Compare 5 and 4: Swap (1, 4, 5, 2, 8)
• Compare 5 and 2: Swap (1, 4, 2, 5, 8)
• Compare 5 and 8: No swap (1, 4, 2, 5, 8)

Iteration 2:

• Compare 1 and 4: No swap (1, 4, 2, 5, 8)
• Compare 4 and 2: Swap (1, 2, 4, 5, 8)
• Compare 4 and 5: No swap (1, 2, 4, 5, 8)
• Compare 5 and 8: No swap (1, 2, 4, 5, 8)

Iteration 3:

• Compare 1 and 2: No swap (1, 2, 4, 5, 8)
• Compare 2 and 4: No swap (1, 2, 4, 5, 8)
• Compare 4 and 5: No swap (1, 2, 4, 5, 8)
• Compare 5 and 8: No swap (1, 2, 4, 5, 8)

Since no swaps were made in Iteration 3, the array is sorted: [1, 2, 4, 5, 8].

Code Example:

for i in range(len(array) - 1):
    for j in range(len(array) - i - 1):
        if array[j] > array[j + 1]:
            array[j], array[j + 1] = array[j + 1], array[j]

Complexity:

• Time Complexity: O(n^2) - Bubble Sort has a quadratic time complexity, making it inefficient for large datasets.
• Space Complexity: O(1) - Bubble Sort has a constant space complexity, as it only requires a few temporary variables for swapping.

Advantages:

• Simple to implement: Bubble Sort is easy to understand and code.
• In-place sorting: It sorts the array without using any extra space.

Disadvantages:

• Slow for large datasets: Its time complexity is high, making it unsuitable for large datasets.
• Not stable: Bubble Sort is not a stable sorting algorithm.

Conclusion:

Bubble Sort is a basic sorting algorithm that is easy to implement but inefficient for large datasets. While it may be useful for small arrays or educational purposes, more efficient algorithms like Merge Sort or Quick Sort are generally preferred for real-world applications.