**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^{2} 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
^{2}i.e. O(n^{2}).

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