Bubble Sort Algorithm

In this tutorial, you will learn how the bubble sort works. Also, you will find examples of bubble sort in C ++

Bubble sort is an algorithm that compares nearby objects and changes their positions if they are not in the required sequence. Order can be ascending or descending.

How does the Bubble sort work?
1-From the first index, compare the first and second elements, if the first item is larger than the second element, it is exchanged.

Now, compare the second and third elements. Swap if they are random.

The above process continues until the last one.

Compare the adjacent elements

2-The same process continues in the remaining repetition. After each repetition, the largest of the unplanned element is placed at the end.

In each iteration, comparisons occur until the last random element.

The array is organized when all unplanned elements are placed in their proper places.

Compare the adjacent elements

Compare the adjacent elements

Compare the adjacent elements

Bubble Sort Algorithm

bubbleSort (list)
  of i <- 1 to indexOfLastUnsortElement-1
    if leftElement> rightElement
      switch leftElement and rightElement
finish bubbleSort

Example in c++

// Bubble sort in C++

#include <iostream>
using namespace std;

void bubbleSort(int array[], int size) {

  // run loops two times: one for walking throught the array
  // and the other for comparison
  for (int step = 0; step < size - 1; ++step) {
    for (int i = 0; i < size - step - 1; ++i) {

      // To sort in descending order, change > to < in this line.
      if (array[i] > array[i + 1]) {

        // swap if greater is at the rear position
        int temp = array[i];
        array[i] = array[i + 1];
        array[i + 1] = temp;
      }
    }
  }
}

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

// driver code
int main() {
  int array[] = {-3, 40, 0, 21, -100};
  int size = sizeof(array) / sizeof(array[0]);
  bubbleSort(array, size);
  cout << "Sorted Array in Ascending Order:\n";
  printArray(array, size);
}

Optimized Bubble Sort

The code can be modified by introducing additional dynamic variables. After each repetition, if no exchanges occur at that time, there is no need to make any more loops.

In such a case, the swapped is set to false. Therefore, we can prevent further iterations.

bubbleSort(array)
  swapped <- false
  for i <- 1 to indexOfLastUnsortElement-1
    if leftElement > rightElement
      swap leftElement and rightElement
      swapped <- true
finish bubbleSort

Example in c++

// Optimized bubble sort in C++

#include <iostream>
using namespace std;

void bubbleSort(int array[], int size) {
  for (int step = 0; step < size - 1; ++step) {
// Run loops two times: one for walking throught the array
    // and the other for comparison
    int swapped = 0;
    for (int i = 0; i < size - step - 1; ++i) {
      // To sort in descending order, change > to < in this line.
      if (array[i] > array[i + 1]) {

        // Swap if greater is at the rear position
        int temp = array[i];
        array[i] = array[i + 1];
        array[i + 1] = temp;
        swapped = 1;
      }
    }

    // If there is not swapping in the last swap, then the array is already sorted.
    if (swapped == 0)
      break;
  }
}

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

// Driver code
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);
}

Complexity

Bubble Sort is one of the easiest sorting algorithms. Only two loops are required in the algorithm.

CycleNumber of Comparisons

1st(n-1)

2nd(n-2)

3rd(n-3)

………….last1

Number of comparisons: (n — 1) + (n — 2) + (n — 3) +…..+ 1 = n(n — 1) / 2 nearly equals to n²

Complexity: O(n²)

Also, we can analyze the difficulty by simply looking at the number of loops. There are 2 loops so the weight is n * n = n²

Time Issues:

Worst Case Complexity: O (n²)
If we want to sort in ascending order and the array is in descending order then, the worst case occurs.

Best Case Complexity:O (n)
If the default array is already set, then there is no need to filter.

Average Case Complexity:O (n²)
Occurs when elements of the array are jumbled.

Bubble Sort Applications

Bubble sort is used in the following cases where

1. the complexity of the code does not matter.
2. short code is preferred.