Data Structure: Bubble Sort?

What is a bubble sort technique?

Not the most efficient technique in terms of time complexity, but hey it can be optimized. The bubble sort technique, in a nutshell, is taking an array of adjacent items and comparing one to the next. If for any reason the items do not go from increasing order the element will be swapped.

How does it work

We can take an example array of [4,6,1,7,3,2,5]. We can start by iterating through the array.

Notice how we are starting to decrementing instead of incrementing the array. This is because we want to decrement each time we go through an item.

Once the first iteration is established we can begin our second set of iteration. We won’t need to decrement. We can increment through each item like this.

Now it’s time to set our conditional statement. Our main purpose is to swap if the current item is greater than the next.

Furthermore, we swap our items. And return the array. Here is a full solution below.

What is the time complexity?

Given the fact we had to iterate twice the time complexity for this technique runs an O(n)² making it the worst-case scenario. However, it can be optimized.



Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store