Optimizing Bubble Sort Algorithm

Having been in Java world for around 5 years, I believe Bubble Sort is the probably simplest and widely used sorting algorithm that works by repeatedly swapping the adjacent elements if they are not in the right order. However, with just a little tweaking, it’s possible to make it more efficient. So, we will first see what Bubble Sort algorithm is and then move to its optimization part.

To sort the entire array, the array is traversed n-1 time (array having n elements). These are called passes. In the first pass the largest element moves to the last position (sorting in ascending order). So if the original (unsorted) array is:

55           33           99           77           44

During the first iteration, adjacent elements will be compared, and swapped if larger element is on left side), as shown below:

After first iteration, the largest element is at the last position.

33          55        77          44         99

Now, in the 2nd pass, we will consider the first (n-1) elements only (because last position already has largest element). After 2nd pass the array will be

33           55           44           77           99

i.e., 77 will be moved to the (n-1)th position. 

After (n-1) iterations, (n-1) elements will be moved to their proper positions, the last element has to be the smallest. So the array will be sorted after n-1 passes.

Algorithm:

void bubbleSort(int array[], int n) {

       for (int i = 0; i < n; i++) {

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

                     if (array[j] > array[j + 1]) {

                           int temp = array[j + 1];

                           array[j + 1] = array[j];

                           array[j] = temp;

                     }

              }

       }

}

Time Complexity: O(n*n)

Auxiliary Space: O(1)

Boundary Cases: Bubble sort takes minimum time (Order of n) when elements are already sorted.

Sorting In Place: Yes

Stable: Yes

Improvement (Optimization):

In the above example, the array got sorted after 2nd pass, but we will still continue with the 3rd, 4th pass. Suppose if the array is already sorted, then there will be no swapping (because adjacent elements are always in order), but still we will continue with the passes and there will still be (n-1) passes.

If we can identify, that the array is sorted, then we should stop execution of further passes. This is the optimization over the original bubble sort algorithm.

If there is no swapping in an iteration pass, it means the array has become sorted, so algorithm should be smart enough to skip further iterations.

For this we can have a flag variable which is set to true before each pass and is made false when a swapping is performed.

void optimizedBubbleSort(int array[], int n) {

       for (int i = 0; i < n; i++) {

              boolean flag = true;

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

                     if (array[j] > array[j + 1]) {

                           flag = false;

                           int temp = array[j + 1];

                           array[j + 1] = array[j];

                           array[j] = temp;

                     }

              }

              // No Swapping happened, array is sorted

              if (flag) {

                     return;

              }

       }

}

For the best case (array already sorted) the optimized algorithm will be O(n).

For average case also, the performance will see an improvement. Whereas the original algorithm was O(n²) for all the cases.