Introduction

Sorting is a fundamental operation in computer science, and there are various algorithms to accomplish this task. One of the simplest sorting algorithms is the Bubble Sort. While not the most efficient for large datasets, understanding Bubble Sort can be a great way to grasp the basic principles of sorting algorithms. In this post, we'll explore what Bubble Sort is and how to implement it in Python.

What is Bubble sort

Bubble Sort is a comparison-based sorting algorithm that repeatedly steps through the list to be sorted. It compares adjacent elements and swaps them if they are in the wrong order. The algorithm continues iterating through the list until no more swaps are needed, indicating that the list is now sorted.

The main idea behind Bubble Sort is that larger elements "bubble up" to the end of the list, while smaller elements "sink" to the beginning.

How Bubble Sort Works

Let's have two versions: for a child and for adults

For a child

Imagine you have a bunch of colorful balls, and you want to arrange them in order from the lightest to the heaviest. The Bubble Sort method is a way to do this. Here's how it works:

1. Comparing and swapping balls
   • You start by looking at the first two balls. If the first ball is heavier than the second one, you swap them. So now, the heaviest ball comes after the lighter ball.
   • You move on to the next pair of balls and do the same thing. Keep doing this for all the pairs of balls in your collection.
2. One round of comparing and swapping
   • After you've gone through all the pairs, you'll notice that the heaviest balls have bubbled up to the end of the row
   • Now, you don't touch the heaviest ball anymore, because it's in the right place.
   • You start over again but only look at the balls before the heaviest ball. You compare and swap them if needed
3. Repeating until sorted
   • You keep doing these rounds of comparing and swapping, but each time, you focus on the fewer and fewer balls because the heaviest ones are already in place.
   • You repeat this process until no more swaps are needed in a round. This means the balls are all in order, just like you wanted!!!
4. Bubble Sort is like bubble rising

The reason it's called Bubble Sort is that it's like bubbles rising in a fizzy drink. The biggest bubbles rise to the top first, then the smaller ones follow.

So on simple words, Bubble Sort is like arranging colorful balls by looking at pairs of balls and swapping them if they're in the wrong order. You repeat thus until the balls are lined up from lightest to heaviest, just like the bubbles in your drink.

For an adult

Bubble Sort is a simple sorting algorithm that works by repeatedly stepping through a list of elements (like numbers or words), comparing each pair of adjacent items, and swapping them if they're in the wrong order. The pass through the list is repeated for as many times as there are elements in the list. The algorithm gets its name because the smaller elements "bubble" to the top of the list like air bubbles in water, while the larger elements "sink" to the bottom.

Let's break this into more understandable words

1. Comparison and swapping
   The algorithm starts by comparing the first two elements in the list. If the first element is greater than the second, it swaps them. This process continues for every adjacent pair of elements in the list.
2. One pass through the list
   • After this first pass through the list, the largest element has bubbled up to the last position.
   • The algorithm then performs the same comparison and swapping process for the remaining elements in the list, excluding the last one.
3. Repeat until sorted
   • The algorithm keeps repeating these passes through the list until no more swaps are needed. This means that all elements are in their correct sorted positions.
   • During each pass, smaller elements "bubble up" to their appropriate positions.
4. Optimization
   A small optimization can be applied by introducing a flag that keeps track of whether any swaps were made during a pass. If no swaps were made, it means the list is already sorted, and the algorithm can stop early.
5. Time Complexity
   • In the worst case, Bubble Sort requires n passes through the list, where n is the number of elements. For each pass, it compares and possibly swaps adjacent elements.
   • This results in a time complexity of O(n^2), which means the algorithm's performance becomes slow for large lists.

In summary, while Bubble Sort is conceptually simple and easy to understand, it's not very efficient for large datasets due to its quadratic time complexity. It's mainly used for educational purposes and understanding sorting concepts. For practical applications, more advanced sorting algorithms like Quick Sort, Merge Sort, or built-in sorting functions in programming languages are preferred due to their better performance.

Implementation using Python

Here's a simple step-by-step implementation of the Bubble Sort algorithm in Python (Flagged Optimized Bubble Sort) which involves using a flag to determine whether any swaps were made during an iteration. If no swaps are made, the algorithm knows that the array is already sorted and can terminate early.

from typing import List, Any

def bubble_sort(collection: List[Any]) -> List[Any]:
    n = len(collection)

    for i in range(n):
        swapped = False  # Initialize the flag
        for j in range(0, n-i-1):
            if collection[j] > collection[j+1]:
                collection[j], collection[j+1] = collection[j+1], collection[j]  # Swap the elements
                swapped = True
        if not swapped:
            break  # No swaps were made, collection is sorted

    return collection

def main():
    # Input collection from the user
    input_str = input("Enter a collection separated by a comma:")
    input_list = [x.strip() for x in input_str.split(',')]

    # Print sorted collection
    print(*bubble_sort(input_list), sep=",")

if __name__ == "__main__":
    main()

This implementation of Bubble Sort with The Flagged Optimized Bubble Sort approach can be summarized as follows:

1. Start by assuming that a swap has not occurred during the current iteration.
2. Traverse the array, comparing adjacent elements.
3. If an element on the left is greater than the element on the right, swap them and set the flag to indicate that a swap occurred.
4. After completing the inner loop for one full iteration, check if the flag is still false. If it is, the array is already sorted, and the algorithm can terminate early.
5. Repeat steps 2 to 4 until no more swaps are made in a complete iteration.

This optimized approach will potentially reduce the number of iterations and comparisons in cases where the array is already sorted or nearly sorted, making the Bubble Sort algorithm slightly more efficient.

Bubble Sort in real world applications

In the real world, Bubble Sort is rarely used for practical applications due to its inefficiency compared to other sorting algorithms. However, it still has some limited use cases and can be valuable for educational purposes. Here are a few scenarios where Bubble Sort might be used:

1. Educational Purposes: Bubble Sort is often used in programming courses to teach basic sorting concepts. Its simple implementation helps beginners understand how sorting algorithms work.
2. Small Datasets: If you have a very small number of items to sort, Bubble Sort might be acceptable since its performance issues are not as pronounced with small data sets.
3. Already Partially Sorted Data: If you're dealing with data that is already mostly sorted, Bubble Sort's adaptive nature (it becomes more efficient with fewer swaps as it progresses) might make it a viable choice.
4. Learning Algorithms: Bubble Sort can be used as a stepping stone to learn about other, more efficient sorting algorithms. It's a good starting point before moving on to more complex techniques.

However, for the most practical scenarios, especially those involving larger data sets, you would prefer more efficient sorting algorithms like Quick Sort, Merge Sort, or the built-in sorting functions provided by programming languages (e.g., sorted() in Python). These algorithms offer significantly better performance and are better suited for real-world applications where efficiency matters.

Conclusion

Bubble Sort is a basic sorting algorithm that serves as a foundation for understanding more complex sorting methods. While it's not the most efficient algorithm for large datasets, it's a great starting point to learn about the principles of sorting and algorithm optimization. As you delve further into the world of computer science, you'll encounter more advanced sorting algorithms that offer better performance.

Remember, understanding Bubble Sort is like learning to ride a bicycle before moving on to a motorbike. It equips you with valuable insights into sorting techniques that will be useful when exploring more sophisticated algorithms.