Bubble Sort and its Analysis

Bubble sort is a really weird name but this algorithm actually bubbles up the largest element at the end after each iteration and that's why the name is Bubble Sort.

bubble of larger elements in bubble sort

In this algorithm, we start with iterating over an array and compare the first element to the second one and swap them if they are in the wrong order and then compare the second and the third one and so on. After this iteration, the largest element goes to the last of the array as shown in the picture given below.

iteration in bubble sort

Now the largest element is already in the last position, so we again repeat this process, leaving the elements which are already in their correct positions and this gives us a sorted array.

bubble sort

animation of bubble sort

We can write the entire process in the following steps:

Start iterating over the array.
Compare the adjacent elements. For example, the first and second, second and third, etc.
Swap them if they are not in order.
Repeat these steps except for the elements which are placed at their correct positions.

Now, the next part is to write a code for Bubble sort and implement these logics.

Code for Bubble Sort

We have to start by iterating over the array. So, let's use a for loop for that - for i in 1 to A.length. Now we have to repeatedly compare the adjacent elements and swap them if they are in the wrong order (see the above picture). Also at the end of the initial for loop, the largest element is at the end of the array, so this repetition should not be done for those elements which are already at correct place. So, we can iterate with a variable 'j' from 1 to A.length-i and then compare the j^th and j+1^th elements i.e., for j in 1 to A.length-i -> compare A[j] and A[j+1]. Here, A.length-i will make the iteration not touch the elements which are already at their correct position. For example, in the first iteration, none of the elements are at correct position, so j will go up to A.length-1 and thus compare A[A.length-1] and A[A.length] at the last; similarly, at the second iteration, the last element is at the correct position, so j will go up to A.length-2 and compare A[A.length-2] and A[A.length-1] and hence leaving the last element i.e., A[A.length] and so on.

code for bubble sort

So, let's write the full code for Bubble sort.

Bubble-SORT(A)
  for i in 1 to A.length
    for j in 1 to A.length-i
      if A[j] > A[j+1]
        swap(A[j], A[j+1])

The first loop (for i in 1 to A.length) is for iterating over the array. Now for every iteration, we are again iterating from the first element of the array to the (A.length-i)^th element (for j in 1 to A.length-i) and then comparing A[j] and A[j+1].

After the comparison, we are swapping A[j] and A[j+1] if they are in the wrong order.

C
Python
Java

#include <stdio.h>

// function to swap values of two variables
void swap(int *a, int *b) {
  int temp;
  temp = *a;
  *a = *b;
  *b = temp;
}

void bubble_sort(int a[], int size) {
  int i, j;
  for(i=0; i<size; i++) {
    for(j=0; j<size-i-1; j++) {
      if (a[j] > a[j+1]) {
        swap(&a[j], &a[j+1]);
      }
    }
  }
}

int main() {
  int a[] = {4, 8, 1, 3, 10, 9, 2, 11, 5, 6};
  bubble_sort(a, 10);

  //printing array
  int i;
  for(i=0; i<10; i++) {
    printf("%d ",a[i]);
  }
  printf("\n");
  return 0;
}

def bubble_sort(a):
  for i in range(0, len(a)):
    for j in range(0, len(a)-i-1):
      if (a[j] > a[j+1]):
        a[j], a[j+1] = a[j+1], a[j]

if __name__ == '__main__':
  a = [4, 8, 1, 3, 10, 9, 2, 11, 5, 6]
  bubble_sort(a)
  print(a)

class Bubble {
  public static void bubbleSort(int a[]) {
    for(int i=0; i<a.length; i++) {
      for(int j=0; j<a.length-i-1; j++) {
        if(a[j] > a[j+1]) {
          int temp = a[j];
          a[j] = a[j+1];
          a[j+1] = temp;
        }
      }
    }
  }

  public static void main(String[] args) {
    int a[] = {4, 8, 1, 3, 10, 9, 2, 11, 5, 6};
    bubbleSort(a);

    //printing array
    for(int i=0; i<10; i++) {
      System.out.print(a[i] + " ");
    }
    System.out.println("");
  }
}

One thing anyone should note here is that even if the array gets sorted in the middle of the process, there is no mechanism to stop the process and the process will continue to occur unnecessarily. So, this is where we can optimize our algorithm.

Optimized Version of Bubble Sort

To check if the array is sorted or not, we can check if any element is getting swapped in the iteration or not. If none of the elements are getting swapped, then it means that the array is sroted and we can stop the process of Bubble Sort.

So, let's use a variable to keep the record of swapping and modify the previous code according to it.

Bubble-SORT-OPTIMIZED(A)
  for i in 1 to A.length
    swapped = FALSE
    for j in 1 to A.length-i
      if A[j] > A[j+1]
        swap(A[j], A[j+1])
        swapped = TRUE
    if not(swapped)
      break

Here, we are using an extra variable 'swapped' to store whether we are swapping in the middle of the algorithm or not. We are setting the 'swapped' value to true after swapping something - swapped = TRUE and at last, we are checking if something was swapped or not in the process - if not(swapped), then we are breaking the loop if nothing was swapped and hence meaning that the loop is already sorted.

C
Python
Java

#include <stdio.h>

// function to swap values of two variables
void swap(int *a, int *b) {
  int temp;
  temp = *a;
  *a = *b;
  *b = temp;
}

void optimized_bubble_sort(int a[], int size) {
  int i, j;
  for(i=0; i<size; i++) {
    int swapped = 0;
    for(j=0; j<size-i-1; j++) {
      if (a[j] > a[j+1]) {
        swap(&a[j], &a[j+1]);
        swapped = 1;
      }
    }
    if(!swapped)
      break;
  }
}

int main() {
  int a[] = {4, 8, 1, 3, 10, 9, 2, 11, 5, 6};
  optimized_bubble_sort(a, 10);

  //printing array
  int i;
  for(i=0; i<10; i++) {
    printf("%d ",a[i]);
  }
  printf("\n");
  return 0;
}

def optimized_bubble_sort(a):
  for i in range(0, len(a)):
    swapped = False
    for j in range(0, len(a)-i-1):
      if (a[j] > a[j+1]):
        a[j], a[j+1] = a[j+1], a[j]
        swapped = True

    if(not (swapped)):
      break

if __name__ == '__main__':
  a = [4, 8, 1, 3, 10, 9, 2, 11, 5, 6]
  optimized_bubble_sort(a)
  print(a)

class Bubble {
  public static void optimizedBubbleSort(int a[]) {
    for(int i=0; i<a.length; i++) {
      boolean swapped = false;
      for(int j=0; j<a.length-i-1; j++) {
        if(a[j] > a[j+1]) {
          int temp = a[j];
          a[j] = a[j+1];
          a[j+1] = temp;
          swapped = true;
        }
      }
      if(!swapped)
        break;
    }
  }

  public static void main(String[] args) {
    int a[] = {4, 8, 1, 3, 10, 9, 2, 11, 5, 6};
    optimizedBubbleSort(a);

    //printing array
    for(int i=0; i<10; i++) {
      System.out.print(a[i] + " ");
    }
    System.out.println("");
  }
}

Analysis of Bubble sort

Let's first talk about the non-optimized version of the Bubble sort.

Non-Optimized Bubble Sort

Regardless of the input, the two loops and the if statements are going to execute every time. Only the execution of the swap statement will depend upon the input.

So, every time the first for loop (for i in 1 to A.length) is going to execute n+1 times (n is the size of the array 'A' and 1 extra time when the condition of the loop will be check and failed) and the second for loop is going to execute (n-i)+1 times for every iteration of the outer loop. For example, it is going to execute (n-1)+1 times for the first iteration of the outer loop (when i is 1), (n-2)+1 times in the second iteration of the outer loop (i is 2) and so on. So, it will run a total of $(n) + (n-1) + ... + 1 = \frac{(n)(n+1)}{2}$ times.

Now, the if statement is going to run every time the statements of inner loop are going to be executed i.e., $(n-1) + (n-2)+ ... +1 = \frac{(n-1)(n)}{2}$ times.

Till now, we know that our running time is going to be quadratic regardless of the input. The swap statement can run a minimum of 0 times when the array is already sorted or a maximum of $\frac{(n-1)(n)}{2}$ times (equal to the number of times if is executed). In both cases, the rate of the growth of our function will be quadratic because we already have quadratic terms in our function ($\frac{(n)(n+1)}{2}$ and $\frac{(n-1)(n)}{2}$). So, the running time of this algorithm is $\Theta(n^2)$.

Optimized Bubble Sort

In the worst case, there won't be any difference between the optimized and the non-optimized versions because the worst case will be when the break statement never gets executed and this is going to occur when the array is sorted in the reverse order.

Thus, the optimized version has $O(n^2)$ worst case running time.

Now, let's talk about the best case. The best case would be when the outer for loop (for i in 1 to A.length) just breaks after its first iteration. And this can occur when there is nothing swapped inside the second loop which means the array is already sorted.

best case in bubble sort

In this case, the outer for loop will run only one time and the inner for loop will run n times and then the algorithm will stop. So, the best case running time of this algorithm is going to be a linear one and thus this algorithm has $\Omega(n)$

Thus, we have seen two sorting algorithms till now. Both of these algorithms are coding implementations of how we basically sort in our real life. And this is exactly what we need to develop our algorithms. First, think and solve the problem in our mind. If we are able to do so then implementing that solution in code is not going to be a difficult task after going through all the algorithms in this course.

I do not fear computers. I fear lack of them.

- Isaac Asimov