Trusted answers to developer questions

How to implement Bubble sort

Get Started With Data Science

Learn the fundamentals of Data Science with this free course. Future-proof your career by adding Data Science skills to your toolkit — or prepare to land a job in AI, Machine Learning, or Data Analysis.

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(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;
}

RELATED TAGS

sort

algorithms

Learn in-demand tech skills in half the time

PRODUCTS

Mock Interview

New

Courses

Skill Paths

Projects

Assessments

How to implement Bubble sort

The steps in the algorithm

Implementation