The **Bubble sort** is a simple sorting algorithm that continues to swap adjacent values, if they are in the incorrect order, until all the values are sorted. 

# The steps in the algorithm

To sort an array of size *n* in ascending order, it performs *n-1* iterations and in each iteration:
1. It scans through the entire array.
2. It compares element at index `i` with the element at `i`+1.
3. If the element at ​position `i` is greater than the element at `i`+1, then the elements are swapped.

On average, this algorithm takes $O(n^2)$ time (where *n* is the size of the array). The algorithm can be optimized to take $O(n)$, if an array is already sorted in the required order, by breaking the outer for-loop if no element is swapped in the inner for-loop.

The following illustration shows the algorithm in action:

#include <iostream>
using namespace std;

int main() {
 int arrayA[] = {3, 2, 1, 0};
 // Finding the size of the array
 auto n = end(arrayA) - begin(arrayA);
 // 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(arrayA[i] > arrayA[i + 1]){
       // Since the element at i is greater,
       //swap elements at index i and i+1
       int temp = arrayA[i];
       arrayA[i] = arrayA[i + 1];
       arrayA[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<< arrayA[i] << " ";
}
 return 0;
}

JavaScript

arrayA = [3, 2, 1, 0]
# Finding the size of the array
n = len(arrayA)
# Sorting array_A in ascending order
for it in range(n-1):
 flag = 0
 for i in range(n-1):
     # Comparing adjacent elements
     if arrayA[i] > arrayA[i + 1]:
     # Since the element at i is greater,
     # swap elements at index i and i+1
         temp = arrayA[i]
         arrayA[i] = arrayA[i + 1]
         arrayA[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(arrayA)

How to implement Bubble sort

The steps in the algorithm

Implementation