Bubble Sort

Lesson 13 of 26 in Coddy's Arrays in C++ course.

Another way of sorting an array is called bubble sort. The idea is that we compare each close pair of numbers and swap if the right number is smaller than the left until we reach the end.

1. Declare the variable named counter and initialize it with 1. The counter keeps the count of elements that are sorted.

2. Create a while loop with a condition of iteration till the counter is less than n.

int counter=1;
while(counter<n){
     
}

3. Create a for loop inside while loop and iterate it from 0 to n-counter time. Because the counter number of elements is sorted and we don't need to check them again.

int counter=1;
while(counter<n){
     for(int i=0;i<n-counter;i++){
     
     }
}

4. then compare the ith element with its next one that is with (i+1)th and if arr[i]>arr[i+1] swap them.

we can see that in the first iteration of the external while loop the largest element got pushed back to the last position and that is why we ignore that part for the next iteration and for that we increment the counter by 1.

int counter=1;
while(counter<n){
  for(int i=0;i<n-counter;i++){
    if(arr[i]>arr[i+1]){
      int temp=arr[i];
      arr[i]=arr[i+1];
      arr[i+1]=temp;
    }
  }
  counter++;
}

Time complexity Analysis

We are running a while loop n times and in each while loop, a for loop runs almost n times therefore the time complexity becomes O(n²).

To see how actually the algorithm works step by step.

Bubble Sort Visualiser

Challenge

Sort the given array using the bubble sort algorithm and print every element whose index is odd. Separate elements by a single space.

Try it yourself

#include<iostream>
using namespace std;


int main(){
  
int n;
cin>>n;
int arr[n];
for(int i=0;i<n;i++){
  cin>>arr[i];
}

//Code Here




return 0;

}