Bubble Sort Algorithm With Example

Bubble Sort: The algorithm works by comparing each item in the list with the item next to it, and swapping them if required. In other words, the largest element has bubbled to the top of the array. Bubble sorting is one of the simplest sorting algorithm that we can use to sort an array or a structure. The algorithm repeats this process until it makes a pass all the way through the list without swapping any items.

Note:- Since the algorithm is implemented with the help of 2 FOR loops only, it can be used as such for any programming languages like C/C++ or Java.

In this article you can find the Algorithm of bubble sort,Properties of bubble sort, discussion of bubble sort And at last example of bubble sort.

Bubble Sort Algorithm 

void bubbleSort(int ar[])
{
   for (int i = (ar.length - 1); i >= 0; i--)
   {
      for (int j = 1; j ≤ i; j++)
      {
         if (ar[j-1] > ar[j])
         {
              int temp = ar[j-1];
              ar[j-1] = ar[j];
              ar[j] = temp;
   } } } }

Bubble Sort Algorithm Properties: 

• Stable
• O(1) extra space
• O(n2) comparisons and swaps
• Adaptive: O(n) when nearly sorted

In the case of Bubble sort, the best case is when the array to be sorted is in the perfect order(in the sorted order).  The worst case of bubble sort is when we need to sort an array arranged in descending order to be sorted in ascending order or vice versa.

Bubble Sort Algorithm Discussion: 

Bubble sort has many of the same properties as insertion sort, but has slightly higher overhead. In the case of nearly sorted data, bubble sort takes O(n) time, but requires at least 2 passes through the data (whereas insertion sort requires something more like 1 pass).

Bubble Sort Algorithm Example:

Here is one step of the algorithm. The largest element - 7 - is bubbled to the top:

7, 5, 2, 4, 3, 9

5, 7, 2, 4, 3, 9

5, 2, 7, 4, 3, 9

5, 2, 4, 7, 3, 9

5, 2, 4, 3, 7, 9

5, 2, 4, 3, 7, 9

The worst-case runtime complexity is O(n2). See explanation below

Implementation Bubble Sort Algorithm in C++

#include <cstdlib>
#include <iostream>
using namespace std;
 
void print_array(int array[], int size) {
 cout<< "buble sort steps: ";
 int j;
 for (j=0; j<size;j++)
 cout <<" "<< array[j];
 cout << endl;
}//end of print_array
 
void bubble_sort(int arr[], int size) {
 bool not_sorted = true;
 int j=1,tmp; 
 
 while (not_sorted)  {
 not_sorted = false;
 j++;
 for (int i = 0; i < size - j; i++) {
 if (arr[i] > arr[i + 1]) {
 tmp = arr[i];
 arr[i] = arr[i + 1];
 arr[i + 1] = tmp;
 not_sorted = true;
 
    }//end of if
   print_array(arr,5);
  }//end of for loop
 }//end of while loop
}//end of bubble_sort
 
int main() {
 int array[5]= {5,4,3,2,1};
 print_array(array,5);
 bubble_sort(array,5);
 return 0;
}//end of main

Implementation Bubble Sort Algorithm in C

#include<stdio.h>
#include<conio.h>
void main()
{
 int i,n,temp,j,arr[25];

 printf("Enter the number of elements in the Array: ");
 scanf("%d",&n);
 printf("\nEnter the elements:\n\n");
 
 for(i=0 ; i<n ; i++)
 {
  printf(" Array[%d] = ",i);
  scanf("%d",&arr[i]);
 }
 
 for(i=0 ; i<n ; i++)
 {
  for(j=0 ; j<n-i-1 ; j++)
  {
   if(arr[j]>arr[j+1]) //Swapping Condition is Checked
   {
    temp=arr[j];
    arr[j]=arr[j+1];
    arr[j+1]=temp;
   }
  }
 }
 
 printf("\nThe Sorted Array is:\n\n");
 for(i=0 ; i<n ; i++)
 {
  printf(" %4d",arr[i]);
 }
 getch();
}

Output Screen: