Bubble Sort

Introduction

Bubble sort is a sorting algorithm that compares two adjacent elements and swaps them until they are not in the intended order. It is the simplest sorting algorithm.

How does Bubble Sort work?

Suppose we have an array [-2, 45, 0, 11,-9] that we are willing to sort in ascending order.

1. First Iteration or First Pass

Starting with index zero, compare the first and second elements.

If the first element is greater than the second element, swap them.

Compare the second and third elements, and swap them if the second element is greater than the third element.

Repeat the above process till the last element

2. Remaining Iteration

The same process goes on for the remaining iterations. We will notice that after each iteration, the largest element among the unsorted elements is placed at the end.

In each iteration, the comparison takes place up to the last unsorted element.

The array is sorted when all the unsorted elements are placed at their correct positions.

Algorithm

bubbleSort(array)
  for i <- 1 to indexOfLastUnsortedElement-1
    if leftElement > rightElement
      swap leftElement and rightElement
end bubbleSort

Code Implementation

In Java

package algorithms.sorting;

import java.util.Arrays;

public class BubbleSort {
    public static void main(String[] args) {
        int[] nums = {-2, 45, 0, 11,-9};
        BubbleSort bs = new BubbleSort();
        int swaps = bs.sort(nums);
        System.out.println(Arrays.toString(nums));
        System.out.println("Total swaps done : " + swaps);
    }

    public int sort(int[] arr) {
        int swaps = 0;

        for (int i = 0; i < arr.length; i++) {
            for (int j = 1; j < arr.length - i; j++) {
                if (arr[j] < arr[j - 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j - 1];
                    arr[j - 1] = temp;
                    swaps++;
                }
            }
        }
        return swaps;
    }
}

In Python

def bubble_sort(array):
    swaps = 0
    for i in range(len(array)):
        for j in range(1, len(array) - i):
            if array[j] < array[j - 1]:
                temp = array[j]
                array[j] = array[j-1]
                array[j-1] = temp
                swaps += 1

    return swaps


if __name__ == '__main__':
    nums = [-2, 45, 0, 11, -9]
    total_swaps = bubble_sort(nums)
    print(nums)
    print(f"Total swaps done : {total_swaps}")

Output

[-9, -2, 0, 11, 45]
Total swaps done : 6

Optimized Bubble Sort Algorithm

One thing, we can notice in the above algorithm is that even if the array is already sorted, the comparisons are still done which is useless. This increases the execution time.

To solve this, we can take an extra boolean variable swapped or isSwapped which is set to true if there occurs swapping of elements. Otherwise, it is set false.

After an iteration, if there is no swapping, the value of swapped or isSwapped will be false. This means elements are already sorted and there is no need to perform further iterations.

This will reduce the execution time and helps to optimize the bubble sort.

Algorithm for Optimized Bubble Sort

bubbleSort(array)
  swapped <- false
  for i <- 1 to indexOfLastUnsortedElement-1
    if leftElement > rightElement
      swap leftElement and rightElement
      swapped <- true
end bubbleSort

Code Implementation

In Java

package algorithms.sorting;

import java.util.Arrays;

public class BubbleSort {
    public static void main(String[] args) {
        int[] nums = {-2, 45, 0, 11,-9};
        BubbleSort bs = new BubbleSort();
        int swaps = bs.sort(nums);
        System.out.println(Arrays.toString(nums));
        System.out.println("Total swaps done : " + swaps);
    }

    public int sort(int[] arr) {
        boolean isSwapped;
        int swaps = 0;

        for (int i = 0; i < arr.length; i++) {
            isSwapped = false;
            for (int j = 1; j < arr.length - i; j++) {
                if (arr[j] < arr[j - 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j - 1];
                    arr[j - 1] = temp;
                    isSwapped = true;
                    swaps++;
                }
            }
            if (!isSwapped) break;
        }
        return swaps;
    }
}

In Python

def bubble_sort(array):
    swaps = 0
    for i in range(len(array)):
        is_swapped = False
        for j in range(1, len(array) - i):
            if array[j] < array[j - 1]:
                temp = array[j]
                array[j] = array[j-1]
                array[j-1] = temp
                is_swapped = True
                swaps += 1

        if not is_swapped:
            break

    return swaps


if __name__ == '__main__':
    nums = [-2, 45, 0, 11, -9]
    total_swaps = bubble_sort(nums)
    print(nums)
    print(f"Total swaps done : {total_swaps}")

Output

[-9, -2, 0, 11, 45]
Total swaps done : 6

Bubble Sort Complexity

Time Complexity
Best	O(n)
Worst	O(n^2)
Average	O(n^2)
Space Complexity	O(1)
Stability	Yes

Detailed Complexity

Bubble Sort compares the adjacent elements.

Cycle	Number of Comparisons
1st	(n-1)
2nd	(n-2)
3rd	(n-3)
.......	......
last	1

Hence, the number of comparisons is

(n-1) + (n-2) + (n-3) +.....+ 1 = n(n-1)/2

which is nearly equal to n^2

Hence, Complexity: O(n^2)

Time Complexity

Worst Case Complexity: O(n^2) If we want to sort in ascending order and the array is in descending order then the worst case occurs.

Best Case Complexity: O(n) If the array is already sorted, then there is no need for sorting.

Average Case Complexity: O(n^2) It occurs when the elements of the array are in jumbled order (neither ascending nor descending).

Space Complexity

Space complexity is O(1) because an extra variable is used for swapping.

In the optimized bubble sort algorithm, two extra variables are used. Hence, the space complexity will be O(2).

Conclusion

In this blog, we discussed the first sorting algorithm - Bubble Sort. This blog post cannot end without thanking the person who has motivated a lot of students to learn DSA, that too free of cost - Kunal Kushwaha and Community Classroom. You can also access his free DSA playlist here.

Image Courtesy: Programiz
Visualize algorithms easily on visualgo.net.