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)

Python

How to implement Bubble sort

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:  It scans through the entire array. It compares element at index i with the element at i+1. 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(n2)O(n^2)O(n2) time (where n is the size of the array). The algorithm can be optimized to take O(n)O(n)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: 

How to implement Bubble sort

The steps in the algorithm

Implementation