What the heck is bubble sort?
For this week’s post, I decided to write about a common algorithm problem. In this post, I plan on going overwhat bubble sort is and break down how I would approach solving the algorithm.
Bubble sort is a simple sorting algorithm that looks at an array of elements. It works by repeatedly swapping the adjacent elements of the array until it is sorted in order.
Under the hood
In this example I will be outlining an example of how bubble sort works for a five element array.
- Start with the first two elements of the unsorted array.
- Compare elements number 1 and 2. Swap the order if the second is less than the third
- Compare elements number 2 and 3. Swap the order if the third is less than the second.
- Compare elements number 3 and 4. Swap the order if the fourth is less than the third.
- Compare elements number 4 and 5. Swap the order if the fifth is less than the fourth.
The image below is a visual example of what I just outlined step by step.
The example below is bubble sort written as a function.
As you can see below, this solution for Bubble Sort runs has exponential time complexity. In referring to my previous post Big O Notation, O(N²) is always bad news and will slow down significantly if the array plugged into the function gets larger.
The double for loop in this function is used to sort the whole array. If one loop is used, the first two elements will be the only elements that are sorted. Additionally, what this means is that if the array is already sorted, it will take only one iteration.
Bubble sort is one of the simpler concepts to understand when it comes to algorithms. For my future posts, I plan on going over merge and selection sort.
