Bubble Sort

Bubble Sort

Bubble sort is the simplest kind of sorting method. In this method we do this bubblesort procedure in several iteration, which is called passess. This sort is that compares two adjacent elements and repeatedly swapping them until they are not in the calculated order.

Algorithm

In the algorithm suppose arr is an array of n elements and swap function is used to swap the values of given array elements.

begin BubbleSort(arr)  
   for all array elements  
      if arr[i] > arr[i+1]  
         swap(arr[i], arr[i+1])  
      end if  
   end for     
   return arr     
end BubbleSort

Working of Bubblesort Algorithm

Let elements of array are –

First Pass

Sorting will start from the first two elements. And compare first and second element to check which is greater.

Here, 32 is greater than 13, so there is no swapping requires as it is already sorted. then, compare 32 with 26.

Here, 26 is smaller than 36. So, swapping is needed.

Now, compare 32 and 35.

Here, 32 is smaller than 35. So, it is already sorted.

Now, the comparison between 35 and 10.

Here, 35 is greater than 10 that are not sorted. So, swapping is needed.

Now, move to the second iteration.

Second Pass

The above same process will be followed for second iteration.

Here, 32 is greater than 10. So, swapping is needed.

Move to the third iteration.

Third Pass

The above same process will be followed for third iteration.

Here, 26 is greater than 10. So, swapping is needed.

Move to the fourth iteration.

Fourth pass

After the fourth iteration,

Hence, Here  no swapping required, so the array is completely sorted

Bubblesort complexity

1. Time Complexities

• Worst Case Complexity: O(n²)
• Best Case Complexity: O(n)
• Average Case Complexity: O(n²)

2. The space complexity

O(1)

Program for Bubble Sort in C

#include <stdio.h>

void bubbleSort(int arr[], int size) {
int i;
int j;

  // loop for accesing element
  for (j = 0; j < size - 1; ++j) {
      
    // loop for comparing elements
    for (i = 0; i < size - j - 1; ++i) {
      
      // comparing two adjacent elements
      if (arr[i] > arr[i + 1]) {
        
        // swapping 
        int temp = arr[i];
        arr[i] = arr[i + 1];
        arr[i + 1] = temp;
      }
    }
  }
}

// print array
void printArray(int arr[], int size) {
  for (int i = 0; i < size; ++i) {
    printf("%d  ", arr[i]);
  }
  printf("\n");
}

int main() {
  int data[] = {-2, 45, 0, 11, -9};
  

  int size = sizeof(data) / sizeof(data[0]);

  bubbleSort(data, size);
  
  printf("Sorted Array in Ascending Order:\n");
  printArray(data, size);
}

Output

Sorted Array in Ascending Order:
-9  -2  0  11  45

Program for Bubble Sort in C++

#include <iostream>
using namespace std;

void bubbleSort(int arr[], int size) {
int i;
int j;

  // loop for accessing element
  for (j = 0; j < size; ++j) {
      
    // loop for comparing elements
    for (i = 0; i < size - j; ++i) {

      // compare two elements
      if (arr[i] > arr[i + 1]) {

        // swapping element
        int temp = arr[i];
        arr[i] = arr[i + 1];
        arr[i + 1] = temp;
      }
    }
  }
}

// print array
void printArray(int arr[], int size) {
  for (int i = 0; i < size; ++i) {
    cout << "  " << arr[i];
  }
  cout << "\n";
}

int main() {
  int data[] = {-2, 45, 0, 11, -9};
  
  int size = sizeof(data) / sizeof(data[0]);
  
  bubbleSort(data, size);
  
  cout << "Sorted Array in Ascending Order:\n";  
  printArray(data, size);
}

Output

Sorted Array in Ascending Order:
  -9  -2  0  11  45

Program for Bubble Sort in Python

def bubbleSort(array):
    
  # loop for accessing element
  for i in range(len(arr)):

    # loop for comparing elements
    for j in range(0, len(arr) - i - 1):

      # comparing two elements
      if arr[j] > arr[j + 1]:

        # swapping elements 
        temp = arr[j]
        arr[j] = arr[j+1]
        arr[j+1] = temp


data = [-2, 45, 0, 11, -9]

bubbleSort(data)

print('Sorted Array in Ascending Order:')
print(data)

Output

Sorted Array in Ascending Order:
[-9, -2, 0, 11, 45]

Program for Bubble Sort in Java

import java.util.Arrays;

class Main {

  static void bubbleSort(int arr[]) {
    int size = arr.length;
    int i;
    int j; 
    
    // loop for accessing element
    for (i = 0; i < size - 1; i++)
    
      // loop for comparing elements
      for (j = 0; j < size - i - 1; j++)

        // comparing two elements
        if (arr[j] > arr[j + 1]) {

          // swapping 
          int temp = arr[j];
          arr[j] = arr[j + 1];
          arr[j + 1] = temp;
        }
  }

  public static void main(String args[]) {
      
    int[] data = { -2, 45, 0, 11, -9 };
    
    Main.bubbleSort(data);
    
    System.out.println("Sorted Array in Ascending Order:");
    System.out.println(Arrays.toString(data));
  }
}

Output

Sorted Array in Ascending Order:
[-9, -2, 0, 11, 45]

Optimized Bubblesort Algorithm

Algorithm for optimized bubble sort

bubbleSort(arr)  
n = length(arr)  
repeat  
  swapped = false  
  for i = 1 to n - 1  
         if arr[i - 1] > arr[i], then  
         swap(arr[i - 1], arr[i])  
         swapped = true  
         end if  
   end for  
   n = n - 1  
 until not swapped  
end bubbleSort

BubbleSort Applications

• complexity does not matter
• short and simple code is preferred

Read more, Bellman Ford’s Algorithm