
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 n2 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 n2 i.e. O(n2).
You can try the practical of bubble sort on the virtual labs that provide some better understanding.