Home » Bubble sort algorithm

C++ programmingAlgorithmsData structures

Bubble sort algorithm

Arpit Jain

May 13, 2021

0

SaveSavedRemoved 0

Definition of Bubble sort

Bubble sort algorithm is a type of sorting that compares all the ‘n’ number of elements one by one for sorting. It sorts the values in the increasing order of their numeric value. Bubble sort starts sorting with the first two elements.  It compares the element to check which one is greater. After comparing it arranges them in their ascending order. Bubble sort takes the order of n² time for the sorting. Time complexity is O(n^2). Space complexity is O(1).

Topics Covered

• Definition
• Example of bubble sort with diagram
• Algorithm for bubble sort
• C program to implement bubble sort
• C++ program to implement bubble sort
• Advantages of bubble sort
• Disadvantages of bubble sort

Example of bubble sort algorithm

This diagram shows how the bubble sort works.

Algorithm for bubble sort

bubble sort (array)
for (i <- 1) to (index of last unsorted element-1)
   if
    left element > right element
    swap left element and right element
exit bubble sort

C program to implement bubble sort

#include <stdio.h>
#include <conio.h>
void bubbleSort(int array[], int size)
{
// run loops two times: one for walking throught the array
  // and the other for comparison
  for (int step = 0; step < size - 1; ++step) {
    for (int i = 0; i < size - step - 1; ++i) {
       // To sort in descending order, change">" to "<".
      if (array[i] > array[i + 1]) {
         // swap if greater is at the rear position
        int temp = array[i];
        array[i] = array[i + 1];
        array[i + 1] = temp;
      }
    }
  }
}
// function to print the array
void printArray(int array[], int size) {
  for (int i = 0; i < size; ++i) {
    printf("%d  ", array[i]);
  }
  printf("\n");
}
// driver code
int main() {
  int data[] = {-2, 45, 0, 11, -9};
  int size = sizeof(data) / sizeof(data[0]);
  bubbleSort(data, size);
  printf("Sorted Array in Ascending Order:\n");
  printArray(data, size);
}

C++ program to implement bubble sort

#include<iostream>
using namespace std;
int main()
{
int n;
cout<<"Enter the value of size of the array "<<endl;
cin>>n;
 int arr[n];
 //apply the loop for taking the input in the array
 cout<<"Enter the values in the array :"<<endl;
 for(int i=0; i<=n;i++)
 {
 	cin>>arr[i];
 }	
  //apply two loops for bubble sorting
  for(int i=1; i<=n; i++)
  {
  	for(int j=0; j<=n-i; j++)
  	{
  		if(arr[j]>arr[j+1])
  		{
  			int temp = arr[j];
  			arr[j] = arr[j+1];
  			arr[j+1] = temp;
		  }
	  }
  }
  //apply the loop for printing the final sorted array
  cout<<"The sorted array is :"<<endl;
  	for(int i=0; i<=n; i++ )
	{
		cout<<arr[i]<<" ";
	}
	return 0;
}

Advantages of bubble sort

• The bubble sort acquires less amount of memory than other sorting algorithms and also have smaller codes.
• As it’s best running time is O(n), it can more efficiently work for smaller as well as for array that contains some sorted elements.

Disadvantages of bubble sort

• The bubble sort algorithm is not efficient for larger items as its complexity is in order of n² i.e. O(n²).

You can try the practical of bubble sort on the virtual labs that provide some better understanding.