Bubbleology — The Study of Bubble Sort

Every time someone mentions Bubble Sort, it’s always either about:

  1. The simplest sorting algorithm to start with.
  2. An example of sorting algorithm NOT to be used.

Also, the President of the United States says you shouldn’t use it.

So, when I started with my #100DaysOfCode journey for becoming a better Software engineer, I decided to dive deeper into each algorithm rather than blindly believing it.

Time to Burst the Bubble!

 

What’s in a name? Everything!

The bubble sort gets its name because elements tend to move up into the correct order like bubbles rising to the surface.

Source: Wikipedia

The smaller values gradually “bubble” their way upward to the top of the array while the larger values sink to the bottom of the array. Bubble sort sometimes referred to as Sinking sort, is considered simplest sorting algorithm.

Know Thy Bubbling Basics :

Bubble Sort compares each successive pair of elements in an unordered array and swaps the elements if they are not in order.

The following example illustrates the bubble sort on the unordered list {6, 5, 3, 1, 8, 7, 2, 4}. Here, the pairs which are compared are encapsulated in ‘**’

{**6, 5**, 3, 1, 8, 7, 2, 4}     
# Compare 6 and 5. Since 6 > 5 -> Perform swap
{5, **6, 3**, 1, 8, 7, 2, 4} 
# Compare 6 and 3. Since 6 > 3 -> Perform swap
{5, 3, **6, 1** , 8, 7, 2 ,4} 
# Compare 6 and 1. Since 6 > 1 -> Perform swap
{5, 3, 1, **6, 8**, 7, 2, 4} 
# Compare 6 and 8. Since 6 < 8 -> No swap
{5, 3, 1, 6, **8, 7**, 2, 4}
# Compare 8 and 7. Since 8 > 7 -> Perform swap
{5, 3, 1, 6, 7, **8, 2**, 4} 
# Compare 8 and 2. Since 8 > 2-> Perform swap
{5, 3, 1 ,6, 7, 2, **8, 4**}
# Compare 8 and 2. Since 8 > 4 -> Perform swap
{5, 3, 1, 6, 7, 2, 4, 8}

After one iteration through the list, we have the greatest value in the array at the final position. Thus, to be sure the list is sorted, we must iterate n-1 times for lists of length n.

Graphic:

Compares two elements at a time and makes a swap if the 2nd element is larger than the first

Show me the code!

 

The bubble_sort() function iterates over the array in two for loops and compares the values of two elements in the array at a time. It swaps the larger value with smaller value and continues to do so in the loop until the array is fully sorted.

Properties Stack :

Looking at you, Bubble Sort! (Source: Reddit)

 

Bubble Sort isn’t the most efficient sorting algorithm, but hey even Rome wasn’t built in O(1).

A) Best Case Time Complexity: O(n)

Best case occurs when the elements in the array are already sorted. Let’s try this same algorithm again using the best case scenario with sorted array.

{**1, 2**, 3}     
# Compare 1 and 2. Since 1 < 2 -> No SWAP
{1, **2, 3**} 
# Compare 2 and 3. Since 2 < 3 -> No SWAP

Given an array of n unsorted elements, it takes (n-1) iterations through the array in order to sort it using the bubble sort algorithm.

Here, the number of elements in the array were 3, let’s call n =3. So, to sort these n elements, this algorithms best case will take n-1 iterations, n-1 = O(n)

Optimized Implementation:
The above bubble_sort() function always runs O(n²) time even if the array is sorted. It can be optimized by stopping the algorithm if inner loop didn’t cause any swap by setting a flag.

B) Worst and Average Case Time Complexity: O(n ^ 2)

Since we have a loop nested within another loop, Big O notation of the algorithm will be quadratic. The worst case occurs when elements in the array are reverse sorted.

C) Stable, In place & Space Complexity

  1. Bubble sort is a stable algorithm, meaning that the relative ordering of equal elements shall remain same after the algorithm is executed.
  2. It is also an in-place algorithm, as it operates directly on the inputted data and does not require additional space other than the input data.
  3. The Space complexity is the additional space that you need apart from the initial space occupied by the data. Bubble-sort algorithm uses only a constant additional space, apart from the original data, so it is O(1) in space complexity.

In a nutshell :

  1. Bubble Sort compares each successive pair of elements in an unordered array and swaps the elements if they are not in order.
  2. Given an array of n unsorted elements, it takes (n-1) iterations through the array in order to sort it using the bubble sort algorithm.
  3. This sorting algorithm is preferred when data list to be sorted is tiny.
  4. Bubble sort is time-consuming but doesn’t consume a lot of resources (low space complexity).

Have a Dekko :

Here are some helpful resources I referred to while studying Bubble Sort:

  1. Bubble Sort, Harvard CS50
  2. Bubble Sort Explanation, GeeksForGeeks
  3. Bubble-sort with Hungarian folk dance

Challenge Accepted!

Now, try this Bubble Sort Algorithm Challenge to apply your knowledge

Final Bubble Sort Code In Python

Bubble Sort Algorithm Challenge Solution

Get new blog posts delivered straight to your inbox. No Spam. I Promise.

Email *


You may also like

Leave a Reply

Your email address will not be published. Required fields are marked *