Bubble Sort Algorithm – With Time And Space Complexity

What is Bubble Sort?

Bubble Sort Algorithm is a sorting algorithm which is based on the continuous comparison of Adjacent elements in a given array in each pass, such that if the first element of the two adjacent elements compared at this time is larger than the second element, it is swapped to take the position of the smaller element.

In this tutorial, we will first discuss how bubble sort algorithm works, then we will discuss the time and space complexity of bubble sort algorithm.

How Bubble Sort Algorithm Works

Let us use the below array elements to learn how Bubble sort algorithm works.

So we have an array of five elements (from the image above) to be sorted using bubble sort algorithm; our expected output is this: A = {2,3,5,7,8}.

For quick understanding of what’s going on, i will arrange the array elements vertically without the index (as shown in the following image).

We will compare consecutive adjacent elements each time, if the first element is greater that the second, we will swap and change their positions; they first element will take the position of the second (lesser) element, we will do this for each pass until we finish sorting the array elements. Note that the sorted element in each pass is the element with the highest value that is yet to be sorted. Again note that once an element has been sorted to its right position, the next pass of sorting will not consider elements from that last sorted element and beyond – because the are already sorted.

A pass is when the highest element to be sorted has been sorted to its right position (as you will soon discover in the following imagery illustrations).

So if we compare the first two elements, 8 is greater that 5: so we swap them; 8 takes the position of 5, while 5 takes the position of 8.

What we have now is A = {5,8,7,3,2} as can be seen in the image above.

Next we compare the elements 8 and 7. 8 is greater than 7, therefore we swap their positions in the array and 8 takes the place of 7 while 7 takes the place of 8.

So what we have now is A = {5,7,8,3,2} as can be seen in the image above.

Again we compare the values 8 and 3 and 8 is still greater than 3, so we swap the positions of 8 and 3.

So what we have now is A = {5,7,3,8,2} as can be seen in the image above.

Finally for this round we compare elements 8 and 2, obviously 8 is greater than 2 and so we swap again. 8 takes the position of 2 while 2 takes the position of 8.

So what we have now is A = {5,7,3,2,8} as can be seen in the image above.

Note that in this example we were given 5 elements in the array A = {8,5,7,3,2} and so there will be only 4 possible pairs of elements for comparison. We have compared all four possible pairs in this round.

Earlier on i said i was going to explain what a pass is. Now when all elements are compared once, this is known as a pass. Pass means we are going through the given list or array elements and for us we have just completed the first pass.

What is the result of the first pass? One element is sorted. Which element is sorted? 8 is sorted or bubbled to its right position in the list.

Therefore in each pass, the element with the greatest value is sorted.

In the next pass, we will not consider any element from 8 and beyond – because they have already been sorted.

Note also that in this first pass, we have made 4 comparisons. They thing to remember is that if there are n elements in the array, we must do n – 1 comparisons. And in the second pass, n becomes n- 1 (because we are not considering 8 anymore), therefore the no. of comparisons will be n – 1 – 1 comparisons. Third pass will be n – 2 – 1 comparisons, fourth pass will be n – 3 – 1 comparisons and so on.

So this is what our array looks like now: A = {5,7,3,2,8}. For the second pass, we start by comparing elements 5 and 7; 5 is not greater than 7 and so there is no swap, we move to the next comparison which is 7 and 3; 7 is greater than 3 and so we swap them. What we now have is: A = {5,3,7,2,8}. And then we do the last comparison which is 7 and 2, 7 is greater than 2 and so we swap and what we now have is: A = {5,3,2,7,8}. We have completed this pass and we already have two elements sorted in their correct order; the two greatest elements in the list: 7 and 8. How many comparisons were there? 3 comparisons as stated before.

This is what we have now A = {5,3,2,7,8}, we continue with the third pass. We compare elements 5 and 3; 5 is greater, we swap – what we have now is A = {3,5,2,7,8}. We compare the elements 5 and 2; 5 is greater, we swap – what we have now is A = {3,2,5,7,8}. We have completed this pass and we already have three elements sorted in their correct order; the three greatest elements in the list: 5, 7 and 8. How many comparisons were there? 2 comparisons as stated before.

This is what we have now A = {3,2,5,7,8}, we continue with the fourth pass. We compare elements 3 and 2; 3 is greater, we swap – what we have now is A = {2,3,5,7,8}. We have completed the fourth pass and we already have all elements sorted in their correct order. How many comparisons were there? Only 1 comparison.

Bubble Sort Time Complexity

The time complexity of any sorting algorithm is given by the number of comparisons carried out by that sorting algorithm.

In our working example, we have 5 elements and we conducted 4 passes to arrive at our expected outcome.

So if there were n elements, we should required n – 1 passes to get at the desired result.

Looking at our comparisons in each pass (for our five elements), first pass = 4 comparisons, second pass = 3 comparisons, third pass = 2 comparisons and fourth pass = 1 comparison.

So we had 1 + 2 + 3 + 4 comparisons for 5 elements in the array,

For n element, we should have 1 + 2 + 3 + 4 … + n – 1 comparisons which is equal to sum of the first n natural numbers,

therefore 1 + 2 + 3 + 4 … + n – 1 = n (n – 1)/2

which is = n² – n/2 and the fastest growing term of the polynomial equation is n², therefore the time complexity of bubble sort is O(n²).

Interesting Points About Bubble Sort

• Why is it called bubble Sort? It is called bubble sort because given a list of elements to be sorted, the heavier elements fall to the bottom of the list from the heaviest to the least heaviest while the lighter elements bubbles up the list. Just like if you throw a stone into water, the stone is heavier so it goes to settle in the bottom of the water container; as it goes down, it causes bubbles and lighter components in the water are carried up along with the bubble effects produce.
• So the effect of bubble sort algorithm is just like the bubbles in water when a heavy thing is thrown into it.
• Another interesting thing: in one pass (i.e the first pass), i got the largest element which is 8; in the second pass i got the two largest element i.e 7 and 8; third pass, three largest element 5,7 and 8; for some n elements, if i perform k passes, i will get k no. of largest elements in their correct order. Now if you have a list and you don’t want to sort everything but you just want to know which element is the greatest element in the given array, just perform 1 pass. If you want to know the two greatest elements, just perform 2 passes; if you want to know the three greatest element, just perform 3 passes and so on. So you can use bubble sort to get just the k no. of greatest element in a list by performing just k no. of passes.

Bubble Sort Pseudocode

Bubble_Sort(list, list_size)
    For i=0 to i<list_size-1
        For j=0 to j<list_size-1-i
            if(list[j] > list[j+1]
                Swap_positions(list[j],list[j+1])
            End if
            Increment j
        End Loop
        Increment i
    End Loop
End

Bubble Sort Pseudocode Explained

Line of code	Explanation
Bubble_Sort(list, list_size)	Function name and takes two parameters: the list or array and the size of the list
For i=0 to i<list_size-1	The outer loop that controls the passes. As already stated, if there are 5 elements in the array, we should have 4 passes, if there are n elements in the array, we should have n – 1 passes
For j=0 to j<list_size-1-i	The inner loop that controls the bubbling of the element with the highest value to its correct position. As already stated, after each pass, we do not have to disturb ourselves comparing the next highest element to be sorted with the elements that are already sorted; hence in each pass, we exclude the elements that are already sorted from the comparison. That is why we have -i in this line of code; we are using it to subtract the elements that are already sorted. Again we have already established that if we have n elements in a particular pass, we are going to have n – 1 no. of comparisons for that pass; that is why we have the -1 in this line of code. So minus 1 which is statutory, then minus i which is the no. of elements that are already sorted.
if(list[j] > list[j+1]	The comparison between contiguous adjacent elements of the array.
End if	The end if delimiter
Increment j	Used to increment j counter. Will not need to be here if you are using for (j=0;j<n-1-i;j++)
End Loop	Make sure to use your closing delimiter for the inner loop
Increment i	Used to increment i counter. Will not need to be here if you are using for (i=0;i<n-1;i++)
End Loop	Make sure to use your closing delimiter for the outer loop
End	Make sure to use your closing delimiter for your function name

Bubble Sort c Implementation

void Bubble(int A[],int n)
{
    int i,j;
    for(i=0;i<n-1;i++)
{
        for(j=0;j<n-i-1;j++)
{
            if(A[j]>A[j+1])
{
                swap(&A[j],&A[j+1]);

            }
        }
    }
}

Is Bubble Sort Adaptive?

Yes Bubble Sort is Adaptive. To prove this, i will take a list which is already sorted to perform bubble sort.

In the first pass we start by comparing elements 2 and 3; 2 is not greater than 3, no swap. Next we compare elements 3 and 5; 3 is not greater than 5, no swap is done. Next we compare elements 5 and 7; 5 is not greater than 7, again no swap. Then we compare elements 7 and 8; 7 is not greater than 8, and again no swap. The entire pass, no swap is done.

If no swap was done, we can say that the elements where already sorted – that is the reason there was no swap.

So i am going to revisit our pseudocode and i am going to tweak it to take care of the no swap situation of an already sorted array elements – there is no point continuing to try to sort an already sorted array elements.

Bubble_Sort(list, list_size)
    int flag;
    For i=0 to i<list_size-1
        flag = 0;
        For j=0 to j<list_size-1-i
            if(list[j] > list[j+1])
                Swap_positions(list[j],list[j+1])
                flag = 1;
            End if
            Increment j
        End Loop
        if(flag==0)
            break out of both inner and outer loop
        End if
        Increment i
    End Loop
End

So what i have done is to add this lines of code to our existing bubble sort algorithm pseudocode.

Line of code	Explanation
int flag;	Declare variable flag of datatype integer
flag = 0;	Initialize flag to zero just before the inner loop
flag = 1;	If a swap happened inside the inner loop then assign the value 1 to the flag
if(flag==0)	If code execution comes out of the inner loop and remains 0, then no swap happened in the inner loop; meaning that all elements of the array are already sorted.
break out of both inner and outer loop	Stop the program because all elements are already sorted.
End if	Remember to close your if statement with the closing delimiter

So as you can see, what we are using the flag variable to do is to determine if the array elements are already sorted so that we do not waste time and resources trying to sort them.

This may happen in any of the passes, once the elements are fully sorted in any of the passes, the flag will indicate and the program will stop.

If the list is already sorted before the program is ever executed, then the program will stop after the very first pass.

Bubble Sort Time Complexity Of an Already Sorted List

An already sorted list performs only one pass and then it will break and so the no. of comparisons for the inner loop will be n – 1 times and of course there will be no second pass or more for the outer loop controlling the passes because the program will terminate after first pass. Therefore the time complexity of an already sorted array or list will be O(n).

So we can then conclude that:

• The minimum time taken by bubble sort algorithm is O(n) – i.e this happens when the elements of the array are already sorted.
• The maximum time taken by bubble sort algorithm is O(n²)

Therefore bubble sort is adaptive.

Is Bubble Sort Adaptive by itself? No it is not adaptive by itself, we made it adaptive by using a flag to determine when the elements of the array are already sorted.

Is Bubble Sort Stable?

To study if bubble sort is stable or not, i have taken another list with duplicate elements shown below.

Note what we are looking for here is to see if the duplicate elements will maintain their order on the list as the elements are sorted using bubble sort algorithm.

In the first pass we compare the element 8 (first on the list) to the element 8 (the second on the list); first 8 is not greater than second 8, so there will be no swapping. Next we compare the element 8 (the second 8) to the element 3; 8 is greater than 3, so we swap and 8 takes the position of 3 while 3 takes the position of 8.

So what we have now is: 8,3,8,5,4. Now notice that no matter what happens, the two duplicate values of 8 will maintain their order. The second 8 first takes it rightful position and eventually the first 8 on the list also comes after the second 8. So at the end of the sorting what we will have is: 3,4,5,8(1^st 8),8(2^nd 8).

Therefore bubble sort is a stable algorithm.

Bubble Sort in c Programming – The Complete and Optimized Code

#include <stdio.h>
#include<stdlib.h>
void swap(int *x,int *y)
{
  int temp=*x;
  *x=*y;
  *y=temp;
}
void Bubble(int A[],int n)
{
  int i,j,flag=0;
  for(i=0;i<n-1;i++)
  {
    flag=0;
    for(j=0;j<n-i-1;j++)
    {
      if(A[j]>A[j+1])
      {
        swap(&A[j],&A[j+1]);
        flag=1;
      }
    }
    if(flag==0)
    break;
  }
}
int main()
{
  int A[]={11,13,7,12,16,9,24,5,10,3},n=10,i;
  Bubble(A,n);
  for(i=0;i<10;i++)
    printf("%d ",A[i]);
  printf("\n");
  return 0;
}

Bubble Sort Space Complexity

Now we look at space complexity bearing in mind that each Initialization of variable takes 1 unit of space.

void Bubble(int A[],int n)
{
  int i,j,flag=0;
  for(i=0;i<n-1;i++)
  {
    flag=0;
    for(j=0;j<n-i-1;j++)
    {
      if(A[j]>A[j+1])
      {
        swap(&A[j],&A[j+1]);
        flag=1;
      }
    }
    if(flag==0)
    break;
  }
}

Line of code	Count of variable Initialization
void Bubble(int A[],int n)	Variable A = n no. of spaces (based on n no. of element – each element takes 1 space), while variable n = 1 space only (its a single variable)
int i,j,flag=0	i = 1 space, j = 1 space and flag = 1 space
for(i=0;i<n-1;i++)	No new initialization of variable
flag=0;	No new initialization of variable
for(j=0;j<n-i-1;j++)	No new initialization of variable
if(A[j]>A[j+1]	No new initialization of variable
swap(&A[j],&A[j+1]);	No new initialization of variable
flag=1	No new initialization of variable
if(flag==0)	No new initialization of variable
break;	No new initialization of variable

To sum up the Count of Variable Initialization we have:

n + 1 + 1 + 1 + 1 which becomes:

n + 4

• Identify the fastest growing term from the derived space complexity equation

The fastest growing term is n

• Remove constant from the derived equation and coefficient from the fastest growing term if any.

So we remove 3 from the equation and we are left with n; there is no coefficient attached to n so we return n as the term that should go into the big O Notation.

Our space complexity for bubble sort algorithm is O(n).

The Auxiliary Space Complexity Of Bubble Sort Algorithm

Auxiliary space is the extra space used by an algorithm. Here int A[] and int n are the given parameter inputs but the extra space created inside the function Bubble(int A[],int n) for use in the algorithm are: int i, j and flag which all takes only 1 unit of space each.

In total, the auxiliary space used by the bubble sort algorithm is 1 + 1 + 1 = 3 units of spaces

Therefore we can conclude that the auxiliary space complexity of bubble sort algorithm is O(1) because 3 is a constant and we represent all constant as 1 in time or space complexity.

And if a sorting algorithm sorts all the elements without using any extra memory or uses an auxiliary space complexity of O(1), then we can say that such a sorting algorithm is an in-place sorting algorithm.