Bubble sort

Bubble sort is perfect for an introduction to sorting algorithms. I believe it is the easiest to understand, although not the most efficient, as you will see in a minute.

How does bubble sort work?

No surprise here, we loop over every element in the provided array but then again for every element we compare it with the next one, if it is bigger we swap, otherwise we keep on looping until the greatest number ends up at the end. And then we go again and loop until the second greatest ends up at the second place from the end etc...

Let's pause for a second, I mentioned swapping but how does it work? Well there are a few ways of doing this but I prefer this one for its clarity — both your teammates and future self will thank you:

function swap(array, idx, idx2) {
  let temp = array[idx];
  array[idx] = array[idx2];
  array[idx2] = temp;
}

We basically create a temp value storing the first value then we override the first value with the second one and finally we use the stored value to override the second value.

So now that we have this out of the way how does bubbleSort work?

function bubbleSort(arr) {
  const sortedArray = [...arr];
  for (let i = sortedArray.length; i > 0; i--) {
    for (let j = 0; j < i - 1; j++) {
      if (sortedArray[j] > sortedArray[j + 1]) {
        swap(sortedArray, j, j + 1);
      }
    }
  }
  return sortedArray;
}

Let's break this down:

• We loop starting from the end so that we can progressively move the greatest element to the end.
• Then we start another loop which will go from the start up to i - 1 meaning we don't loop over the elements that are already sorted (also because we systematically compare the current value with the next one so it prevents us from running out of the array)
• inside the inner loop we check if the next element is greater than the one we are currently looking at
• if it is we swap otherwise we go to the next element.

One step further

Now what if the array is already sorted before looping over every element? Do we really have to keep looping?

I'd say we don't, so we create a variable which holds the fact that the iteration required swapping, if not we break the loop to prevent unnecessary iterations, here's how it looks!

function bubbleSort(arr) {
  let noSwap = true;
  const sortedArray = [...arr];
  for (let i = sortedArray.length; i > 0; i--) {
    noSwap = true;
    for (let j = 0; j < i - 1; j++) {
      if (sortedArray[j] > sortedArray[j + 1]) {
        swap(sortedArray, j, j + 1);
        noSwap = false;
      }
    }
    if (noSwap) break;
  }
  return sortedArray;
}

There you have it an optimized bubble sort, but keep in mind this algorithm is not the most efficient one especially for large datasets!

Performance considerations

Bubble sort is a simple and intuitive sorting algorithm, but it comes with significant performance drawbacks. Here are some key points to consider:

• Worst-case scenario: O(n²) In the worst-case scenario, where the array is sorted in reverse order, bubble sort will have to perform the maximum number of comparisons and swaps. This results in a time complexity of O(n²), where n is the number of elements in the array.
• Best-case scenario: O(n) In the best-case scenario, where the array is already sorted, the optimized version of bubble sort will only require a single pass through the array to confirm that no swaps are needed. This results in a time complexity of O(n).
• Average-case scenario: O(n²) On average, bubble sort will still require a significant number of comparisons and swaps, resulting in an average time complexity of O(n²).

Practical Use Cases

Bubble sort is generally not suitable for large datasets due to its inefficiency. However, it can be useful for educational purposes or for sorting small arrays where simplicity and readability are more important than performance.

Conclusion

Bubble sort is a fundamental sorting algorithm that serves as an excellent introduction to the concept of sorting, but its inefficiency for large datasets highlights the need for more advanced algorithms in practical applications.

As you continue your journey in mastering algorithms, remember that choosing the right algorithm depends on the specific requirements and constraints of your problem.

Happy coding ! 👨🏻‍💻