Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

sort
algorithms

How to implement Bubble sort

Educative Answers Team

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(n2)O(n^2) time (where n is the size of the array). The algorithm can be optimized to take 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:

1 of 20

Implementation

#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
Copyright ©2022 Educative, Inc. All rights reserved
RELATED COURSES

View all Courses

Keep Exploring