Bubble Sort Algorithm And Application(With Code in C++/Python/Java)

Bubble Sort

Bubble sort is an algorithm that sorts a list of items in ascending or descending order by repeatedly iterating through the list and swapping adjacent elements if they are in the wrong order.

Optimized Implementation of Bubble Sort

One way to optimize bubble sort is to use a flag that keeps track of whether any swaps were made during the inner loop. If no swaps were made, then the list is already sorted and we can exit the outer loop early. This optimization can reduce the time complexity of bubble sort from O(n^2) to O(n) in the best case when the list is already sorted.

Here is an example of an optimized implementation of bubble sort in C++:

#include <iostream>
using namespace std;

void bubbleSort(int arr[], int n) {
  bool swapped;
  do {
    swapped = false;
    for (int i = 0; i < n - 1; i++) {
      if (arr[i] > arr[i + 1]) {
        // swap arr[i] and arr[i + 1]
        int temp = arr[i];
        arr[i] = arr[i + 1];
        arr[i + 1] = temp;
        swapped = true;
      }
    }
  } while (swapped);
}

int main() {
  int arr[] = {5, 1, 4, 2, 8};
  int n = sizeof(arr) / sizeof(arr[0]);
  bubbleSort(arr, n);
  for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
  }
  return 0;
}

Working

The algorithm works by iterating through the list and comparing adjacent elements. If the elements are in the wrong order (i.e. the first element is greater than the second element and the list is supposed to be sorted in ascending order, or the first element is less than the second element and the list is supposed to be sorted in descending order), then the elements are swapped. This process is repeated until the list is sorted.

Time complexity

The time complexity of bubble sort is O(n^2) in the worst case and O(n) in the best case. This means that the algorithm takes longer to run on larger lists, and the time it takes to run increases quadratically with the size of the list.

Auxiliary space

The auxiliary space required by bubble sort is O(1), meaning that it does not require any additional space beyond the input array.

Worst case

The worst case for bubble sort occurs when the list is already sorted in the opposite order that it needs to be (i.e. the

list is already sorted in ascending order and needs to be sorted in descending order, or the list is already sorted in descending order and needs to be sorted in ascending order). In this case, the algorithm will have to perform a full pass through the list for every element, resulting in a time complexity of O(n^2).

Best case

The best case for bubble sorting occurs when the list is already sorted in the correct order. In this case, the algorithm will only need to make a single pass through the list and will not have to perform any swaps, resulting in a time complexity of O(n).

Recursive Implementation of Bubble Sort

It is also possible to implement bubble sort using recursion. Here is an example of a recursive implementation of bubble sort in C++:

#include <iostream>
using namespace std;

void bubbleSortRecursive(int arr[], int n) {
  // base case
  if (n == 1) {
    return;
  }

  // iterate through the list and swap adjacent elements if they are in the wrong order
  for (int i = 0; i < n - 1; i++) {
    if (arr[i] > arr[i + 1]) {
      // swap arr[i] and arr[i + 1]
      int temp = arr[i];
      arr[i] = arr[i + 1];
      arr[i + 1] = temp;
    }
  }

  // recursive call on the shortened list
  bubbleSortRecursive(arr, n - 1);
}

int main() {
  int arr[] = {5, 1, 4, 2, 8};
  int n = sizeof(arr) / sizeof(arr[0]);
  bubbleSortRecursive(arr, n);
  for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
  }
  return 0;
}

Applications

Bubble sort is not commonly used in practice due to its slow performance, but it can be useful as a simple and easy-to-understand sorting algorithm for small lists or for educational purposes. It can also be used as a building block for more efficient sorting algorithms.

Here is the bubble sort algorithm in C++:

#include <iostream>
using namespace std;

void bubbleSort(int arr[], int n) {
  for (int i = 0; i < n - 1; i++) {
    for (int j = 0; j < n - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        // swap arr[j] and arr[j + 1]
        int temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
      }
    }
  }
}

int main() {
  int arr[] = {5, 1, 4, 2, 8};
  int n = sizeof(arr) / sizeof(arr[0]);
  bubbleSort(arr, n);
  for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
  }
  return 0;
}

Here is the bubble sort algorithm in Python:

def bubble_sort(arr):
  n = len(arr)
  for i in range(n-1):
    for j in range(n-i-1):
      if arr[j] > arr[j+1]:
        # swap arr[j] and arr[j+1]
        arr[j], arr[j+1] = arr[j+1], arr[j]

arr = [5, 1, 4, 2, 8]
bubble_sort(arr)
print(arr)

Here is the bubble sort algorithm in Java:

public class BubbleSort {
  public static void bubbleSort(int arr[]) {
    int n = arr.length;
    for (int i = 0; i < n - 1; i++) {
      for (int j = 0; j < n - i - 1; j++) {
        if (arr[j] > arr[j + 1]) {
          // swap arr[j] and arr[j + 1]
          int temp = arr[j];
          arr[j] = arr[j + 1];
          arr[j + 1] = temp;
        }
      }
    }
  }

  public static void main(String args[]) {
    int arr[] = {5, 1, 4, 2, 8};
    bubbleSort(arr);
    System.out.println(Arrays.toString(arr));
  }
}