# Bubble sort algorithm

## 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

## 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;
}``````