In our sorting algorithm series of tutorials, today we will focus on the Bubble Sort algorithm. Previously, we looked upon an introduction of sorting algorithms and focused primarily on selection sort. Let us learn about Bubble sort in this guide. Like selection sort, bubble sort is also considered as one of the simplest sorting algorithms. It works on the principle of continuously swapping elements in the list until they are in the correct order.

## Bubble Sort Algorithm

Let’s see how to sort a list of integers given to us in a form of an array. Suppose we have an array of 5 integers named X with unordered numbers. Our aim is to sort the following numbers in increasing order of values by using a bubble sort algorithm.

In this type of algorithm, we will scan the array several times from left to right. Each scan will be considered as one pass on the array.

### First Pass – Bubble Sort

We will first compare the elements at index 0 and index 1. When we will scan the array and we are at a particular position, we will compare the element at that particular position with the adjacent element at the next position. When we are at index 0, then we will compare the element at index 0 and the element at index 1. If the element at the current position is greater than the element at the next position, we will swap the two elements.

Now we have element ‘4’ at index 0 and element ‘1’ at index 1. As 4 is greater than 1 we will swap the two elements:

Now the list of elements will be something like this. ‘1” has moved to index 0 and ‘4’ has moved to index 1.

Now we will move to the next position which is index 1. Check if the element at index 1 is greater than the element at index 2. In our case it is not true so we will not swap the elements and move onto the next index.

For the next position we will again compare the elements of the current position and its adjacent position. For index 2 the element is ‘5’ and its adjacent index 3 has element ‘2’. As 5 is greater than 2 thus we will swap the two elements and they will move to different positions. ‘5’ will move to index 3 and 2 will move to index 2 as shown below:

Now we will move to the next position which is index 3. At index 3 we have the element ‘5’ and index 4 we have the element ‘3’. As 5 is greater than 3 hence we will swap the two elements. Now ‘5’ will move to index 4 and ‘3’ will move to index 3.

As you will notice, this whole process is pushing the highest element towards the higher indices at each step. Our highest element was ‘5’ and by the end of this process it has moved to its appropriate position. After one pass on the array, the highest element will reach the last position. In other words we can say that ‘5’ has ‘bubbled’ up to the right most position in the array.

The first pass on the array is like running a loop from 0 to (n-1) considering ‘n’ is the number of elements in the array. If X[i], the element at position i, is greater than than the element at position (i+1), then we will swap the two elements. Otherwise, we will move to the next position. However for i=n-1, X[i+1] would be out of the range as there is no element after the last one. So instead of running the loop from i=0 to (n-1) we will run it from i=0 to (n-2). We do not want to access an index that will be out of the range of the array.

### Next Pass – Bubble Sort

Now we will perform another pass on the array. Once again we will keep comparing the adjacent elements and swapping then when required. In the next swap, the second largest element will now end up at its appropriate position which is index 3. For our list, the second largest element is ‘4’ and after the first pass in present at index 1. After the second pass completes, this element will bubble up to index 3. Lets see how it happens.

We will first compare the elements at index 0 and index 1. If the element at the current position is greater than the element at the next position, we will swap the two elements. Now we have element ‘1’ at index 0 and element ‘4’ at index 1. As 1 is less than 4 hence we will not the two elements and move ahead to the next position.

Now we will move to the next position which is index 1. Check if the element at index 1 is greater than the element at index 2. In our case it is true so we will not swap the elements and move onto the next index. Now element ‘4’ will move to index 2 and element ‘2’ will move to index 1.

For the next position we will again compare the elements of the current position and its adjacent position. For index 2 the element is ‘4’ and its adjacent index 3 has element ‘3’. As 4 is greater than 3 thus we will swap the two elements and they will move to different positions. ‘4’ will move to index 3 and ‘3’ will move to index 2 as shown below:

**Original list of elements:**

**4,1,5,2,3**

**After first pass:**

**1,4,2,3,5**

**After second pass:**

**1,2,3,4,5**

With every pass on the array, the array will be divided into two parts: the sorted part and the unsorted part. After the first pass, the element at index 4 is sorted and the rest are unsorted. After the second pass all the elements are at their appropriate positions. In our example it only took us two passes on the array to get the list sorted in increasing order of values however it can take several passes until all the elements get sorted.

With each pass, the highest element in the unsorted array will bubble up to the highest index in the unsorted half. In general, if we will conduct (n-1) passes we are guaranteed to be sorted.

## Pseudocode Bubble Sort Algorithm

Below you can view the pseudocode for the bubble sort algorithm:

```
BubbleSort(X,n)
{
for j=1 to n-1
{
for i=0 to n-2
{
if (X[i] > X[i+1])
{
swap(X[i],X[i+1])
}
}
}
}
```

To monitor the time complexity of Bubble Sort algorithm we will make use of the pseudocode given above. The total running time of this algorithm will be the total running time of the statements inside the nested loops.

Assuming the following statements take a constant time C to execute considering the worst case scenario:

```
if (X[i] > X[i+1])
{
swap(X[i],X[i+1])
}
```

Both the outer and inner loops will run (n-1) times. So the total time taken as a function of n will be:

T(n) = (n-1)*(n-1)*C

=(Cn^2)-2Cn+1

Thus, we can say that the time complexity is O(highest order) so O(n^2).

As you may see selection sort also had the same time complexity as that of bubble sort. Both of these are relatively simple sorting algorithms but are not time efficient as compared to other sorting algorithms that we will learn about in later tutorials.

## Improving Time Complexity of Bubble Sort Algorithm

However, we can modify our program code slightly to improve the time complexity in certain cases of Bubble sort.

#### Modification 1

The first thing that we will change is that we do not need to run the loop till (n-2) in all cases. As you already know by now, at any stage during the sorting process, the array will be divided into unsorted and sorted parts. There is no need to go into the sorted part of the array. For the first pass, we will run the inner loop till (n-2). For the second pass we will run the inner loop till (n-3). Likewise, for the third pass, we only need to run the inner loop till (n-4) and so on. In general, we will run the loop till (n-j-1), so when j=1 we will run till (n-2), when j=2 we will run till (n-3) and so on. In this way we are improving the loop logic. However, the time complexity still remains O(n^2).

```
BubbleSort(X,n)
{
for j=1 to n-1
{
for i=0 to n-j-1
{
if (X[i] > X[i+1])
{
swap(X[i],X[i+1])
}
}
}
}
```

#### Modification 2

Let us modify our code further to improve the time complexity. As you may remember the example array we used to demonstrate bubble sort got sorted after only 2 passes. Hence running the loop more times will be redundant. If the list is already sorted, then there will no swaps. If we go to a pass without swapping anything then definitely at that stage the list is already sorted. Using this theory we will modify our algorithm further as shown below:

```
BubbleSort(X,n)
{
for j=1 to n-1
{
flag =0
for i=0 to n-j-1
{
if (X[i] > X[i+1])
{
swap(X[i],X[i+1])
flag=1
}
}
if (flag==0) break
}
}
```

Now we have included a variable called ‘flag’ and set it to zero. This will be used to monitor if we need to continue the loop or not. Once the condition X[i] > X[i+1] is true for any i then we will swap the elements and also set the flag value to 1. When we will come out of this loop, after a pass if is flag =0 then it means there was no swap so we do not need to conduct any more passes. Thus we will break out of this loop. This way we will avoid making unnecessary passes once the array is sorted.

##### Best Case

For the best case, if our array is already sorted, then the inner loop will execute only once to figure out that it is already sorted. Assuming the following statements take time C in the worst case:

```
if (X[i] > X[i+1])
{
swap(X[i],X[i+1])
flag=1
}
```

So now the time taken will be C*(n-1). The best case for our algorithm will be O(n).

In an average case, taking (n/2) passes to exit the loop so the inner loop will also run (n-1) times so time complexity will still be O(n^2)

Bubble sort is in place and a stable sorting algorithm with time complexity ranging from O(n^2) for worst-case and O(n) for the best case.

## Bubble Sort Algorithm Code in C

```
#include <stdio.h>
void
swap (int *xp, int *yp)
{
int temp = *xp;
*xp = *yp;
*yp = temp;
}
void
BubbleSort (int X[], int n)
{
int flag;
for (int i = 0; i < n - 1; i++)
{
flag = 0;
for (int j = 0; j < n - i - 1; j++)
{
if (X[j] > X[j + 1])
{
swap (&X[j], &X[j + 1]);
flag = 1;
}
}
if (flag == 0) break;
}
}
int
main ()
{
int X[] = { 4, 1, 5, 2, 3 };
BubbleSort (X, 5);
for (int i = 0; i < 5; i++)
{
printf ("%d", X[i]);
}
}
```

`12345`