Bubble Sort in Data Structure

Ever witnessed a car racing tournament? There are multiple laps in a race. While the race is in progress, let’s say team A is in 4th position. Team B is just behind team A and Team C is ahead of Team A. Now, in lap 1, if team A is faster than team C, it will overtake it. In other words, teams A and C swap their positions. Similarly, if team E is faster than team F, they will swap positions. In the next lap, Team B and C might swap positions depending on their speed comparisons.

A bubble sort algorithm works in a similar manner. Consider each lap as one iteration. It swaps all the places not in order in a single iteration and moves to the next iteration. Here, we will learn the working of the bubble sort algorithm, and an optimized approach for the same.

Bubble sort

Bubble sort is the simplest sorting algorithm. Sorting is the process of arranging the elements in a dataset either in ascending or descending order. In this comparison-based sorting algorithm, each pair of adjacent elements is compared. If the elements are not found to be in the required order, they are swapped.

1. After each iteration, the largest remaining element is at the highest index. (while arranging in ascending order.)
2. Swaps adjacent elements only.

Working of bubble sort

1. Start for the starting index. Compare the current element to the next element.
2. If the current element and next element are not in order, swap them.
3. Repeat step 2 until you reach the end of the array. This is the end of iteration 1.
4. Repeat steps 1, 2, 3 until the array is sorted.

Bubble Sort Algorithm

Step 1: Repeat For i = 0 to N-1
Step 2: Repeat For j = i + 1 to N - I
Step 3: If Arr[ j ] > Arr[ i ]
             swap Arr[ j ] and Arr[ i ]
             [end of step 2]
             [end of step 1]
Step 4: stop

Bubbel Sort Pseudocode

procedure bubbleSort( array)

   len = array.length;
   
   for i = 0 to loop-1 do:
    
      for j = 0 to loop-1 do:
        
         if list[j] > list[j+1] then
            swap( list[j], list[j+1] )		 
         end if
         
      end for      
   end for
 return array
end procedure

Example of Bubble Sort

Let’s sort the characters in the word “DATAFLAIR” by the bubble sort technique.

ITERATION 1

After iteration 1 ‘T’, the largest element is set at the last position.

ITERATION 2

ITERATION 3

ITERATION 4

ITERATION 5

ITERATION 6

ITERATION 7

ITERATION 8

Stability of Bubble sort algorithm

The stability of sorting algorithms comes into the picture when the same element is present more than once in a dataset. If the same elements in the unsorted dataset appear in the same order in the sorted dataset, then the algorithm is said to be a stable algorithm.

In the above example, the letter ‘A’ appears three times in the original array in the order RED, GREEN, and YELLOW. In the final sorted array after iteration 8, the order of A’s is the same as in the original. Hence, we can say that bubble sort is a stable sorting algorithm.

Implementation of Bubble sort in C

#include <stdio.h>

void main() 
{
   int arr[] = {34,8,25,45,13,70,54,68,100,3,92,86};
  
   int len = 12;
 for (int i = 0; i < len - 1; i++) 
  {
      
    for (int j = 0; j < len - i - 1; j++) 
    {
    
      if (arr[j] > arr[j + 1]) 
      {
      
       int temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
      }
    }
  }
  printf("Sorted Array:\n");
   for (int i = 0; i < len - 1; i++) 
  {
      printf("%d ",arr[i]);
  }
}

Bubble sort Implementation in C++

#include <iostream>
using namespace std;

int main() 
{
   int arr[] = {34,8,25,45,13,70,54,68,100,3,92,86};
  
   int len = 12;
 for (int i = 0; i < len - 1; i++) 
  {
      
    for (int j = 0; j < len - i - 1; j++) 
    {
    
      if (arr[j] > arr[j + 1]) 
      {
      
       int temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
      }
    }
  }
  cout << "Sorted Array:\n";
   for (int i = 0; i < len - 1; i++) 
  {
      cout << " " << arr[i];
  }
}

Bubble sort Implementation in Java

public class Bubblesort 
{
  static void bubbleSort(int arr[]) 
  {
      int i,j,len;
      len = arr.length;
      Boolean swap;
    for (i = 0; i < len - 1; i++)
{
      for (j = 0; j < len - i - 1; j++)
{
        if (arr[j] > arr[j + 1]) 
        {
          int temp = arr[j];
          arr[j] = arr[j + 1];
          arr[j + 1] = temp;
        }
      
    }
}
System.out.println("Sorted Array:");

      for (i = 0; i < len - 1; i++)
      System.out.print(arr[i]+" ");
  }

  public static void main(String args[]) 
  {
      
    int[] data = {34,8,25,45,13,70,54,68,100,3,92,86 };
    Bubblesort.bubbleSort(data);
  }
}

Implementation of Bubble sort in Python

def bubbleSort(array):
   
  for i in range(len(array)):

    for j in range(0, len(array) - i - 1):

      if array[j] > array[j + 1]:

        temp = array[j]
        array[j] = array[j+1]
        array[j+1] = temp


data = [34,8,25,45,13,70,54,68,100,3,92,86]

bubbleSort(data)

print('Sorted Array:')
print(data)

Optimized Bubble sort

In the example we discussed above, you can clearly see that even if the array is sorted, all the comparisons and iterations are still performed. This results in higher execution time, and more comparisons that are useless since the array is already sorted. The last swap in the above example is done in iteration 4. But still, the program continues to compare until iteration 8 which is useless and inefficient.

To counter this problem, we introduce a binary variable that is set to a false value. If even one swap is made in the array during sorting, it changes to true, else it remains false. If after any iteration, it is not changed, then the array is sorted and no need for further comparisons.

In the above example, if we apply optimized bubble sort, then the execution will be stopped after iteration 5 since no swap is made there.

Algorithm of Optimized Bubble Sort

Step 1: Repeat For i = 0 to N-1
             Swap = false
Step 2: Repeat For j = i + 1 to N - I
Step 3: If Arr[ j ] > Arr[ i ]
             swap Arr[ j ] and Arr[ i ]
             swap = true
             [end of step 2]
             If swap == false
             Goto step 4
             [end of step 1]
Step 4: stop

Optimized Bubble Sort Pseudocode

procedure bubbleSort( array)

   len = array.length;
   
   for i = 0 to loop-1 do:
      swap =false	
      for j = 0 to loop-1 do:
        
         if list[j] > list[j+1] then
            swap( list[j], list[j+1] )	
            swap = true	 
         end if         
      end for 
      If swap = = false
      break; 
   end for
 return array
end procedure

Implementation of Optimized bubble sort in C

#include <stdio.h>

void main() 
{
   int arr[] = {34,8,25,45,13,70,54,68,100,3,92,86};
  
   int len = 12, swap;
 for (int i = 0; i < len - 1; i++) 
  {
      swap=0;
    for (int j = 0; j < len - i - 1; j++) 
    {
    
      if (arr[j] > arr[j + 1]) 
      {
      
       int temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
       swap =1;
      }
    }
if (swap == 0)
break;
  }
  printf("Sorted Array:\n");
   for (int i = 0; i < len - 1; i++) 
  {
      printf("%d ",arr[i]);
  }
}

Optimized bubble sort Implementation in C++

#include <iostream>
using namespace std;

int main() 
{
   int arr[] = {34,8,25,45,13,70,54,68,100,3,92,86};
  
   int len = 12,swap;
 for (int i = 0; i < len - 1; i++) 
  {
      swap=0;
    for (int j = 0; j < len - i - 1; j++) 
    {
    
      if (arr[j] > arr[j + 1]) 
      {
      
       int temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
       swap =1;
      }
    }
if (swap ==0)
break;
  }
  cout << "Sorted Array:\n";
   for (int i = 0; i < len - 1; i++) 
  {
      cout << " " << arr[i];
  }
}

Optimized bubble sort Implementation in Java

public class Bubblesort 
{
  static void bubbleSort(int arr[]) 
  {
      int i,j,len;
      len = arr.length;
      Boolean swap;
    for (i = 0; i < len - 1; i++)
{
      swap = false;
      for (j = 0; j < len - i - 1; j++)
{
        if (arr[j] > arr[j + 1]) 
        {
          int temp = arr[j];
          arr[j] = arr[j + 1];
          arr[j + 1] = temp;
          swap = true;
        }
      
    }
if (swap==false)
break;
}
System.out.println("Sorted Array:");

      for (i = 0; i < len - 1; i++)
      System.out.print(arr[i]+" ");
  }

  public static void main(String args[]) 
  {
      
    int[] data = {34,8,25,45,13,70,54,68,100,3,92,86 };
    Bubblesort.bubbleSort(data);
  }
}
}

Implementation of Optimized bubble sort in Python

def bubbleSort(array):
   
  for i in range(len(array)):
    swap = false
    for j in range(0, len(array) - i - 1):

      if array[j] > array[j + 1]:

        temp = array[j]
        array[j] = array[j+1]
        array[j+1] = temp
        swap = true;
    if swap==false:
        break;

data = [34,8,25,45,13,70,54,68,100,3,92,86]

bubbleSort(data)

print('Sorted Array:')
print(data)

Complexity of Bubble Sort

In Bubble sort, adjacent elements are compared.

Total number of comparison : 

(n-1) + (n-2) + (n-3) ………. + 1

= n(n-1)/2 ≈ n^2   ( complexity) 

Best Case Complexity: When elements are already sorted.

Average Case Complexity: When elements are jumbled i.e. they are neither in ascending or descending order.

Worst Case Complexity:  When elements are sorted in the opposite of the required order.

Space complexity: One extra variable, temp,  is used to swap the variables.

Advantages of Bubble sort

1. Used in computer graphics since it can detect very small errors and can fix it in O(2n) time.

2. Easy to Understand.

3. Minimum space requirement as compared to other sorting algorithms.

Disadvantages of bubble sort

1. Not suitable for large datasets.

Conclusion

Bubble sort is the easiest sorting algorithm. Bubble sort is a stable algorithm where the order of the same elements remains unchanged.

Though the worst-case complexity of this algorithm does not make this suitable for very large datasets, by using the optimized version of the bubble, the execution time can be improved to some extent for small datasets. We have also seen the working and implementation of the bubble sort algorithm.