**Bubble Sort** is very popular sorting algorithm in computer programming. Its popularity is not for its performance but for its simplicity. In fact bubble sort is not suitable for most of the practical cases because of its inefficiency. But it very easy to understand and code compare to other sorting algorithms like quick sort or merge sort.

### Bubble Sort Algorithm

Bubble sort algorithm is very simple: continuously swap two adjacent elements if they are not in the right order until no swapping is required.

Two nested loops are generally used in bubble sort implementation. Inner loop starts from the first position and checks whether the element of current position is in desired order with the next element. If not then they are swapped. Then the control moves to the next position and repeats the same thing. After end of every iteration of the outer loop, one element is placed at the right position. For example, we are sorting an array in ascending order, the biggest element comes to the last position after end of the first iteration of the outer loop. Similarly after end of the second iteration, the second biggest element takes the second last position. In this way after *n-1* iterations, *n-1* elements take their right positions and the remaining last element has to be in the right position.

### Graphical Illustration of Bubble Sort

The above diagram shows how the biggest element reaches to the last position of the array after completion of one iteration of outer loop. Similarly after completion of second iteration, the second biggest element will take the second last position. If we continue this process for *n-1* time, then all *n* elements will take their right positions in the final sorted array.

### Implementation of bubble sort in C

Here we’ll discuss about various implementation options of bubble sort in C programming language and their differences.

### Variation 1:

We’ll start with the simplest implementation of bubble sort.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
void bubble_sort(int *arr, int n) { int i = 0, j = 0; int tmp = 0; for(i = 0; i < n-1; i++) { for (j = 0; j < n-1; j++) { if(arr[j+1] < arr[j]) { tmp = arr[j]; arr[j] = arr[j+1]; arr[j+1] = tmp; } } } } |

This is very easy to remember variation. In this case, the outer loop and inner loop both iterate *n-1* times where *n* is not number of elements in the array. The inner loop starts from the first element and checks with the next element whether they are in correct order. If not then swaps the elements. In this example we are sorting the array in ascending order. So if the current element (indexed by *j*) is greater than the next element (indexed by *j+1*), then swap them. After doing this the control moves to the next element. In this case, we’ll have (n-1)*(n-1) comparisons always which is more the the maximum comparison required by bubble sort even in the worst case. In the following sections, we’ll see how we can improve the implementation to minimize number of comparisons.

### Variation 2:

As we discussed earlier, in every iteration of the outer loop, one element of the array is place in the right location. We can use this property to improve our implementation. For every iteration of the outer loop, we’ll iterate the inner loop one less time.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
void bubble_sort(int *arr, int n) { int i = 0, j = 0; int tmp = 0; for(i = 0; i < n-1; i++) { for (j = 0; j < n-i-1; j++) { if(arr[j+1] < arr[j]) { tmp = arr[j]; arr[j] = arr[j+1]; arr[j+1] = tmp; } } } } |

This done by changing the inner loop. We changed the loop from:

1 |
for (j = 0; j < n-1; j++) |

to:

1 |
for (j = 0; j < n-i-1; j++) |

As the value of i increases, the inner loop will iterate less.

### Variation 3:

Our implementation can further be improved by terminating the outer loop if inner loop does not do swapping. If the inner loop does not do swapping, that means the array is already sorted and we don’t need to run the outer loop.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
void bubble_sort(int *arr, int n) { int i = 0; int tmp = 0; int swapped = 0; do { swapped = 0; for (i = 0; i < n-1; i++) { if(arr[i+1] < arr[i]) { tmp = arr[i]; arr[i] = arr[i+1]; arr[i+1] = tmp; swapped = 1; } } n = n - 1; } while (swapped == 1); } |

We changed the outer loop to do-while but could continue with for loop also. In this situation do-while loop is more appropriate the for loop. As we don’t have the outer for loop here, therefore, we don’t have the i variable. To reduce the inner loop iterations, we added the instruction n = n-1 after the end of the inner loop. The inner loop checks whether it does swapping. If it does, then the outer loop continues, otherwise terminates.

### Variation 4:

Our implementation can further be improved. In our previous implementations, we were reducing the inner loop iterations by one for every outer loop iteration. But we can remember where (at which index) we did the last swapping in the inner loop. The rest of the array is already sorted. In the next iteration of the outer loop, we can stop the inner loop where it did swapping in the last iteration.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
void bubble_sort(int *arr, int n) { int i = 0; int tmp = 0; int newn = 0; int swapped = 0; do { swapped = 0; for (i = 0; i < n-1; i++) { if(arr[i+1] < arr[i]) { tmp = arr[i]; arr[i] = arr[i+1]; arr[i+1] = tmp; swapped = 1; newn = i + 1; } } n = newn; } while (swapped == 1); } |

In this implementation, the *newn* remembers where the inner loop did swapping. Next time the inner loop will go up to *newn*. This is the most optimized implementation of bubble sort as per the number of comparisons is concerned.

### Performance of bubble sort

##### Worst Case:

Worst case running time of bubble sort in Big-O notation is O(N_{2}). Worst case scenario occurs when the array is in the opposite order that we are doing sorting for. For example, if we have to sort an array in ascending order the array is in descending order at the beginning.

The above diagram show how our 4 implementations perform in worst case scenarios. Here we’ll see how the number of comparisons increases with the increase of number of input elements. Number of comparisons is directly proportional to the running time requirement. From the graph we can see the the first variation takes maximum number of comparison. Other 3 variation take equal number of comparisons but less than the first variation. We should notice one important thing here that growth rate of all four variations is same. If we double the number of inputs then the number of comparisons will become four times. If we increase the number of elements by four times then the number of comparisons will increase by sixteen times. That means the growth rate is O(N_{2}) in Big-O notation

##### Average Case:

Average case running time of bubble sort in Big-O notation is also O(N^{2}). Average case means at the beginning the array is in random order.

The above diagram shows the performance of our bubble sort implementation is average case. We can see the the first variation takes maximum number of comparisons, then the second one, then third and the fourth variation takes least number of comparison. But here also the growth rate of running time or required comparison is same, i.e. O(N_{2}). If we double the number of inputs, the number of comparisons becomes four times.

##### Best Case:

Best case running time of bubble sort in Big-O notation is O(N). Best case scenario occurs when the array is already sorted at the beginning.

Here we can see that the growth rate of first two variations of our implementations is O(N^{2}). Second variation is slightly better than the first one in terms of actual number of comparisons. But our last two variations perform performs much better than the first two. The growth rate of third and fourth variations is linear. They always take n-1 number of comparisons.