Best Case for Bubble Sort

randerson112358

Aug 19, 2017·4 min read

Bubble Sort Overview

Bubble Sort is considered one of the simplest sorting algorithms that works by repeatedly swapping the adjacent elements if they are in the wrong order. With a bubble sort algorithm you will be able to see that the largest element (assuming we are sorting from smallest to largest) will “bubble” up to the top of the list or array.

Example:
Suppose we want to sort a list or array of elements in ascending order (from smallest to largest): List = (3,1,2)

Using Bubble Sort:
First Pass:
(3,1,2) -> Here the algorithm compares the first two elements (3 & 1)
(1,3,2) -> Here the algorithm swaps 1 and 3 since 1 < 3
(1,3,2) -> Here the algorithm compares the 2nd and 3rd elements (3 & 2)
(1,2,3) -> Here the algorithm swaps 3 and 2since 2< 3

Second Pass: (Depending on which version of the bubble sort algorithm is being used, we will use the one from Wikipedia)
(1,2,3) -> Here the algorithm compares the first two elements (1 & 2)
(1,2,3) -> No SWAPPING , because 1 < 2
(1,2,3) -> Here the algorithm compares the 2nd and 3rd elements (2 & 3)
(1,2,3) -> No SWAPPING , because 2< 3

Since no swapping occurred, this tells us that the array is already sorted in ascending order !

Best Case

Now let’s try this same algorithm again but this time using the best case scenario, which is when the elements are already sorted in the order (ascending)we would like.

(1,2,3) -> Here the algorithm compares the first two elements (1 & 2)
(1,2,3) -> No SWAPPING , because 1 < 2
(1,2,3) -> Here the algorithm compares the 2nd and 3rd elements (2 & 3)
(1,2,3) -> No SWAPPING , because 2< 3

Since no swapping occurred we are done, and the algorithm only did 2 comparisons and the number of elements in the array we will call n=3. So we can see that for n elements this algorithms best case will take only n-1 comparisons, n-1 = O(n)

The procedure or algorithm that we used is below:

This algorithm uses a flag to tell if the elements have been swapped or not, which allows the bubble sort algorithm best case to be O(n) instead of O(n²) like another implementation of bubble sort.

procedure bubbleSort( A : list of sortable items )
    n = length(A)
    repeat 
        swapped = false
        for i = 1 to n-1 inclusive do
            /* if this pair is out of order */
            if A[i-1] > A[i] then
                /* swap them and remember something changed */
                swap( A[i-1], A[i] )
                swapped = true
            end if
        end for
    until not swapped
end procedure

The above algorithm
Worst Case = O(n²)
Best Case = O(n)

Let’s take a look at a different implementation of the bubble sort algorithm:

BUBBLESORT(A)
1 for i = 1 to A.length - 1
2     for j = A.length downto i + 1
3         if A[j] < A[j - 1]
4             exchange A[j] with A[j - 1]

The above algorithm
Worst Case = O(n²)
Best Case = O(n²)

Worst Case

Let’s sort an array or list = (3,2,1)this would be the worst case where the list is in the complete opposite order than that we wish (in ascending order) using the above algorithm.

First Pass:
(3,2,1) -> Compare the elements 3 & 2
(2,3,1) -> Swap 3 & 2 since 2 < 3
(2,3,1) -> Compare the elements 3 & 1
(2,1,3) -> Swap 1 & 3 since 1 < 3

Second Pass:
(2,1,3) -> Compare the elements 2 & 1
(1,2,3) -> Swap 2 & 1 since 1 < 2
(1,2,3) -> Compare the elements 2 & 3
(1,2,3) -> No SWAPPING needed since 2 < 3

We have now finished looping through both loops so the array must be sorted in ascending order.

Notice we made 4 comparisons in the above second example, and the number of elements in the array we will call ’n’ = 3, so the number of comparisons made is (n-1)², and (n-1)² = O(n²)

Also a great book to prepare you for coding/programming interviews is called cracking the coding interview. It will help you familiarize yourself with sorting algorithms and problem solving, so be sure to check it out !

Thanks for reading this article I hope it’s helpful to you all ! Keep up the learning, and if you would like more algorithm analysis videos please visit and subscribe to my YouTube channels (randerson112358 & compsci112358 )

Check Out the following for more content / videos on Algorithm Analysis and Programming:

YouTube Channel:
randerson112358: https://www.youtube.com/channel/UCaV_0qp2NZd319K4_K8Z5SQ

compsci112358:
https://www.youtube.com/channel/UCbmb5IoBtHZTpYZCDBOC1CA

Website:
http://everythingcomputerscience.com/

Video Tutorials on Recurrence Relation:
https://www.udemy.com/recurrence-relation-made-easy/

Video Tutorial on Algorithm Analysis:
https://www.udemy.com/algorithm-analysis/

Twitter:
https://twitter.com/CsEverything

Resources:
Stack Overflow: https://stackoverflow.com/questions/1358383/best-case-for-bubble-sort/45645853#45645853

Wikipedia: https://en.wikipedia.org/wiki/Bubble_sort

GeeksforGeeks: http://www.geeksforgeeks.org/bubble-sort/