Bubble sort. A fairly familiar sorting algorithm I hope. A couple important things you should know abut bubble sort is that it is not fairly popular, not commonly used, and is not that efficient. It is still nice to know just for knowledge sake.
Let's get into it.
What is the goal of this algorithm?
Let's say that we have an array that we want to sort from smallest to largest, so ascending order. We can use bubble sort. The idea is simple, we iterate through the array and for each instance in that array, we will compare it to the instance directly next to it. Let's pretend the first instance is x and the second instance is y. If x = 1 and y = 3, we compared it and we know that the first instance is not greater than the second instance so we move on to the next set of pairs, the second instance we just talked about (y = 3) and the 3rd instance in the array, let's call it z. So now we have y = 3 and z = 2. Since y is greater than z and y comes before z, let's switch out the two so that 2 comes before the 3 which is what we want for an ascending sorted array.
That's the basic idea of bubble sort. That sequence is repeated through out the whole array until everything is right and an iteration with no switches is reached.
Here is a visual representation of that.
Now let's talk time complexity!
To get right to the answer, worst case scenario, bubble sorts time complexity is O(n^2). When actually implementing this algorithm, you began to realize that a nested for-loop is actually required to pull it off.
Top comments (0)