## Bubble Sort Algorithm Logic
In this tutorial, we will learn the logic, complexity, and performance of the bubble sort algorithm, and its implementations in Python, C++, C, and JavaScript.

**Bubble sort** is a naive sorting algorithm that iterates through the list while comparing adjacent elements and swapping their positions if they are in the incorrect order. The element can be ordered in ascending and descending.

The steps in bubble sorting are as follows:
- Beginning with the first index (index = 0), compare the first and second elements. - Swap them if the first element is greater than the second element. - Compare the second and third elements now. If they are not in the right order, swap them.
The same iteration goes on until the last element.
Let’s take an array: [4, 1, 5, 3, 2] .We need to sort this using bubble sort. We have a visual representation of how bubble sort would order the specified array below:

This is the first iteration. And similarly, after all the iterations, the array gets sorted.

## Bubble sort Implementation

Python

# Python program for implementation of Bubble sort
arr = [4, 1, 5, 3, 2] 
# Finding the size of the array
n = len(arr)
# Sorting array_A in ascending order
for it in range(n-1):
  flag = 0
  for i in range(n-1):
    # Comparing adjacent elements
    if arr[i] > arr[i + 1]:
      # Since the element at i is greater,
      # swap elements at index i and i+1
      temp = arr[i]
      arr[i] = arr[i + 1]
      arr[i + 1] = temp
      flag = 1
  # Optimization. Break the outer for loop
  # if no element is swapped in the inner for loop.
  if flag == 0:
    break

# Printing the sorted array
print(arr)

C++

// C++ program for implementation of Bubble sort
#include 
using namespace std;

int main() {
  int arr[] = {4, 1, 5, 3, 2};
  // Finding the size of the array
  auto n = end(arr) - begin(arr);
  // Sorting array_A in ascending order
  for(int it = 0; it < (n - 1); it++){
    int flag = 0;
    for(int i = 0; i < (n - 1); i++){
      // Comparing adjacent elements
      if(arr[i] > arr[i + 1]){
        // Since the element at i is greater,
        //swap elements at index i and i+1
        int temp = arr[i];
        arr[i] = arr[i + 1];
        arr[i + 1] = temp;
        flag = 1;
      }
    }
    // Optimization. Break the outer for loop
    // if no element is swapped in the inner for loop.
    if(flag == 0){
      break;
    }
  }
  // Printing the sorted array
  for(int i = 0; i < n; i++){
    cout<< arr[i] << " ";
  }
  return 0;
}

Javascript

// Javascript program for implementation of Bubble sort
let arr = [4, 1, 5, 3, 2];
let n = arr.length;
// Sorting array_A in ascending order
for(let it = 0; it < (n - 1); it++){
  let flag = 0;
  for(let i = 0; i < (n - 1); i++){
    // Comparing adjacent elements
    if(arr[i] > arrA[i + 1]){
      // Since the element at i is greater,
      //swap elements at index i and i+1
      temp = arrayA[i];
      arr[i] = arr[i + 1];
      arr[i + 1] = temp;
      flag = 1;
    }
  }
  // Optimization. Break the outer for loop
  // if no element is swapped in the inner for loop.
  if(flag == 0){
    break;
  }
}
console.log(arr);

// C program for implementation of Bubble sort 
#include  

void swap(int *xp, int *yp) 
{ 
  int temp = *xp; 
  *xp = *yp; 
  *yp = temp; 
} 

// A function to implement bubble sort 
void bubbleSort(int arr[], int n) 
{ 
  int i, j; 
  for (i = 0; i < n-1; i++)       
  
  // Last i elements are already in place    
  for (j = 0; j < n-i-1; j++)  
  if (arr[j] > arr[j+1]) 
  swap(&arr[j], &arr[j+1]); 
} 

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

// Driver program to test above functions 
int main() 
{ 
  int arr[] = {4, 1, 5, 3, 2}; 
  int n = sizeof(arr)/sizeof(arr[0]); 
  bubbleSort(arr, n); 
  printf("Sorted array: \n"); 
  printArray(arr, n); 
  return 0; 
}

## Complexity Analysis of Bubble Sort
As you can see in the algorithm, We have two loops an outer loop cycle (for traversal) and an inner loop (for comparison)

Total number of comparisons:

  (n - 1) + (n - 2) + (n - 3) +.....+ 1 = n(n - 1) / 2

Approximately equal to (n²)

Time complexity of Bubble Sort: O(n²)
We may also assess the complexity by looking at the number of loops. There are two loops, so the complexity is n*n = n^2.

Space complexity of Bubble Sort: O(1)
Just one extra memory space temp is needed to swap.

Cycle	Number of Comparison
First	(n-1)
Second	(n-2)
Third	(n-3)
...	...
Second Last	2
Last	1

Bubble sort performance and complexity:

Bubble sort Worst case performance	O(n²)
Bubble sort Best case performance	O(n)
Bubble sort Average case performance	O(n²)

##Advantages :
- It is a stable sorting Algorithm i.e. It retains the order of elements in the sorted array the same as the original array.
- It is In-Place Algorithm i.e. It does not require any extra space.
- Bubble Sort is easy to understand and implement.
- Bubble Sort is suitable for "Almost Sorted Array".

##Disadvantages :
- Average and Worst-Case Time Complexity is O (n^2)
- It has more overhead cost as there are more swapping operations compared to other similar algorithms.

## Naive Sorting Algorithms (Bubble, Insertion, Selection)
In this video, we have discussed bubble sort, insertion sort, and selection sort, the most common naive sorting algorithms, and have drawn connections between optimal sorting algorithms (like Quicksort, Merge Sort) and the subroutines found in other interview questions.

Watch Now

Free 5-Day Technical Interview Mini-Course

5 days of pure technical content & in-depth training. No gimmicks, easy unsubscribe if you hate it.