 ## 1. Overview

In this tutorial, we’ll discuss the bubble sort algorithm. We’ll present the pseudocode of the algorithm and analyze its time complexity.

## 2. Algorithm

Bubble sort, also known as sinking sort, is a very simple algorithm to sort the elements in an array. Bubble sort works by continuously swapping the adjacent elements if they appear in the wrong order in the original input list. This swapping process continues until we sort the input list.

In this section, we’ll discuss the steps of bubble sort in detail.

First let’s see the pseudocode of the bubble sort algorithm: Let’s now discuss the steps and the notations used in this algorithm. Note that the goal is to take input array and sort its elements in ascending order.

We start with the first element (index in the array ). Then we check whether the next element (index in ) in the array is greater than the current element or not. If the current element (index in array ) is greater then the next element (index in ), we’ll swap them. If the current element is smaller then the next element, we’ll move to the next element in the array.

In this way, we’ll process and complete the swaps for the whole array. This is the first iteration.

The number of the required iterations is equal to the number of elements in the array. After finishing the required iterations, we’ll get the array sorted in ascending order. We should note, however, that bubble sort can sort things both in ascending and descending order.

In the above bubble sort, there are few issues. In this version, we compare all the pairs of elements for possible swapping. We continue this until we finish the required iterations.

Now let’s assume that the given input array is either nearly or already sorted. Sadly with our current pseudocode, there’s no indicator to indicate that the array is sorted, so we’d still go through all the iterations. Can we improve on this? Let’s see.

After each iteration, let’s keep track of the elements which we swap. If there are no swaps, we can assume that we sorted the input array.

With this assumption, we’re ready to present an improved bubble sort algorithm: Here in this algorithm, we’ve introduced a new variable to keep track of the elements getting swapped. Also, this can indicate whether the given array is already sorted or not during the iteration. So at some point during iteration, if no swaps happen for the entire array, it will come out of the loop and there will be no more iterations required.

## 3. Time Complexity Analysis

### 3.1. Time Complexity of Standard Bubble Sort

In the case of the standard version of the bubble sort, we need to do iterations. In each iteration, we do the comparison and we perform swapping if required. Given an array of size , the first iteration performs comparisons. The second iteration performs comparisons. In this way, the total number of comparison will be: Therefore, in the average case, the time complexity of the standard bubble sort would be .

Now let’s talk about the best case and worst case in bubble sort. The best case would be when the input array is already sorted. In this case, we check all the elements to see if there is any need for swaps. If there is no swapping still we continue and complete iterations. Therefore, in the best scenario, the time complexity of the standard bubble sort would be .

In the worst case, the array is reversely sorted. So we need to do comparisons in the first iteration, in the second interactions, and so on. Hence, the time complexity of the bubble sort in the worst case would be the same as the average case and best case: .

### 3.2. Time Complexity of Improved Bubble Sort

In case of improved bubble sort, we need to perform fewer swaps compared to the standard version. If we talk about time complexity, in the average and the worst-case time complexity would be the same as the standard one: . Though there is an improvement in the efficiency and performance of the improved version in the average and the worst case.

In the best case, when the given array is already sorted, the improved bubble sort achieves better time complexity compared to the standard version.

In this case, given an array, we traverse the list looking for possible swaps. But as the array is already sorted, there will be no swaps. Here we’ll not continue the iterations anymore. Instead, we’ll come out of the loop and the algorithm terminates. In this way, we don’t have to complete all the iterations.

If the given array is sorted, we traverse the array once. So the time complexity in the best case would be .

## 4. Implementation

To see bubble sort in practice please refer to our article on implementing bubble sort in Java.