# Bubble Sort

By | January 2, 2016

# Bubble Sort

Bubble Sort (for ascending order) can be seen as the following steps:

### Algorithm for Bubble Sort:

1. Traverse the given array n = size of array times.
2. Compare adjacent elements of the array.
3. If they are in the wrong order i.e. in descending order then swap them as we want the elements to be in ascending order.

After 1st outer loop iteration, highest element “bubbles up” to the last position.
Then the second highest element “bubbles up” to the second last position and so on.

The largest elements “bubble up” to the top, hence the name of the sorting technique.

### Bubble Sort Example:

```arr[] = {5, 4, 3, 1, 2}
Pass 1:
{5, 4, 3, 1, 2} –> {4, 5, 3, 1, 2}
{4, 5, 3, 1, 2} –> {4, 3, 5, 1, 2}
{4, 3, 5, 1, 2} –> {4, 3, 1, 5, 2}
{4, 3, 1, 5, 2} –> {4, 3, 1, 2, 5}
Pass 2:
{4, 3, 1, 2, 5} –> {3, 4, 1, 2, 5}
{3, 4, 1, 2, 5} –> {3, 1, 4, 2, 5}
{3, 1, 4, 2, 5} –> {3, 1, 2, 4, 5}
Pass 3:
{3, 1, 2, 4, 5} –> {1, 3, 2, 4, 5}
{1, 3, 2, 4, 5} –> {1, 2, 3, 4, 5}```

Elements compared at each step have been shown in bold.

### Bubble Sort Code in C++:

```#include <bits/stdc++.h>
using namespace std;

/*This functions is used to
swap two numbers*/
void swap(int &a,int &b)
{
int temp = a;
a = b;
b = temp;
}

int main() {

int arr[] = {5, 4, 3, 1, 2};
int size = sizeof(arr)/sizeof(arr[0]);

/*Bubble Sort*/
for(int i=0; i<size-1 ; ++i)
{
/*Last i elements are already in place*/
for(int j=0; j<size-i-1 ;++j)
{
/*If adjacent elements are
in wrong order then swap*/
if(arr[j]>arr[j+1])
swap(arr[j], arr[j+1]);
}

/*the part below may be omitted*/
cout<<"Pass "<<i+1<<":\n";

for(int k=0; k<size ; ++k)
cout<<arr[k]<<" ";

cout<<"\n";
}
return 0;
}
```

Output:

```Pass 1:
4 3 1 2 5
Pass 2:
3 1 2 4 5
Pass 3:
1 2 3 4 5
Pass 4:
1 2 3 4 5```

Time Complexity: O(N2)
Auxiliary Space: O(1)