Algorithm Adventures 1: Bubble Sort

“… because sometimes you just need to shake things up a bit.”

Sorting algorithms might not be the most glamorous topic in computer science, but they’re an essential tool for organizing and processing data. So, let’s dive into the wild world of sorting algorithms. From the simplicity of bubble sort to the elegance of merge sort, we’ll explore a variety of algorithms that make it easier to find what you’re looking for. Get ready to sort through the chaos.

What is Bubble Sort?

Sorting algorithms are methods that put a list of things in order, like arranging a deck of cards or sorting a list of names alphabetically.

Bubble sort is a simple and intuitive algorithm that is easy to understand and implement. It works by repeatedly comparing adjacent elements in a collection and swapping them if they are in the wrong order. The algorithm continues to pass through the collection until no more swaps are necessary.

How it works

Let’s walk through a simple example to see how bubble sort works. Consider the following collection of integers: 5, 3, 8, 4, 2. To sort this collection in ascending order using bubble sort, we would start by comparing the first two elements (5 and 3). Since 5 is greater than 3, we swap them, resulting in the collection 3, 5, 8, 4, 2. We then compare the next two elements (5 and 8) and find that they are already in the correct order, so we move on to the next pair (8 and 4). We swap these elements, resulting in the collection 3, 5, 4, 8, 2. We continue this process until we reach the end of the collection and no more swaps are necessary. The final sorted collection is 2, 3, 4, 5, 8.

Here is a PHP implementation of bubble sort:

<?php

function bubbleSort($arr) {
  $n = count($arr);
  for ($i = 0; $i < $n; $i++) {
    for ($j = 0; $j < $n - $i - 1; $j++) {
      if ($arr[$j] > $arr[$j+1]) {
        $temp = $arr[$j];
        $arr[$j] = $arr[$j+1];
        $arr[$j+1] = $temp;
      }
    }
  }
  return $arr;
}

$arr = array(5, 3, 8, 4, 2);
echo "Unsorted array: ";
print_r($arr);

$arr = bubbleSort($arr);
echo "Sorted array: ";
print_r($arr);

As you can see in the example, there is a for loop inside another for loop, this means its worst-case time complexity is O(n²), which means that as the size of the collection grows, the amount of time it takes to sort the collection grows at an exponential rate. This can be a problem for large collections. For 5 elements it’s a maximum of 25 steps, for 10 elements it’s 100 steps…

While bubble sort is easy to understand and implement, it is not the most efficient sorting algorithm.

Is it usefull?

Well, in short, no.

However, bubble sort is still useful in certain situations, such as when sorting small collections or collections that are nearly sorted to begin with. Even for those cases, insertion sort is better. Bubble sort is also a good algorithm to study when first learning about sorting, as it provides a solid foundation for understanding more complex sorting algorithms.

Outside of academia, the only good use case is for checking if the collection is already sorted, as the complexity for a sorted collection is O(n), which is better than more complex sorting algorithms like QuickSort or MergeSort with a best-case complexity of O(n*logn).

Oh, and you may get Bubble sort as a question in an interview for some junior developer roles.

Next time we will look into Insertion sort, another crappy but just a little faster basic sorting algorithm.

Check out other sorting algorithm in this series

Algorithm Adventures 2: Insertion Sort