Bubble Sort

Bubble sort is a simple sorting algorithm that repeatedly steps through an array, compares adjacent elements and swaps them if they are in the wrong order. This is repeated until all elements in the array are in sorted order. Bubble sort is inefficient for real-world use and is primarily used as an educational tool. When Barack Obama was asked about the best way to sort an array of one million numbers, Obama replied “I think the bubble sort would be the wrong way to go.”. Nonetheless, it is still a good algorithm to understand how algorithms work.

Bubble Sort Algorithm

Starting with the first element of the array:

1. Compare the current element with the next element.
2. If the Current Element > Next Element, swap them.
3. Otherwise, move to the next element. Repeat until no swaps occur.

Bubble sort needs an additional pass to know that the array is sorted, that is, it knows that the job is complete if it can run through the entire array without performing any swaps. The algorithm below assumes 0-index array sorted in ascending order.

procedure bubbleSort(A : list of sortable items)
    n := length(A)
    repeat
        swapped := false
        for i := 1 to n-1 inclusive do
            /* if this pair is out of order */
            if A[i-1] > A[i] then
                /* swap them and remember something changed */
                swap(A[i-1], A[i])
                swapped := true
            end if
        end for
    until not swapped
end procedure

Step by Step example

Take an array of numbers “5 1 4 2 8”, and sort the array from lowest number to greatest number using bubble sort. In each step, elements written in bold are being compared. Three passes will be required;

( 5 1 4 2 8 ) → ( 1 5 4 2 8 ), Here, algorithm compares the first two elements, and swaps since 5 > 1.
( 1 5 4 2 8 ) → ( 1 4 5 2 8 ), Swap since 5 > 4
( 1 4 5 2 8 ) → ( 1 4 2 5 8 ), Swap since 5 > 2
( 1 4 2 5 8 ) → ( 1 4 2 5 8 ), Now, since these elements are already in order (8 > 5), algorithm does not swap them.

( 1 4 2 5 8 ) → ( 1 4 2 5 8 )
( 1 4 2 5 8 ) → ( 1 2 4 5 8 ), Swap since 4 > 2
( 1 2 4 5 8 ) → ( 1 2 4 5 8 )
( 1 2 4 5 8 ) → ( 1 2 4 5 8 )

As mention, the array is sorted at this point but the algorithm doesn’t know that it has done its job. It needs one additional pass through the array to know its sorted (that is, no swaps occur.)

( 1 2 4 5 8 ) → ( 1 2 4 5 8 )
( 1 2 4 5 8 ) → ( 1 2 4 5 8 )
( 1 2 4 5 8 ) → ( 1 2 4 5 8 )
( 1 2 4 5 8 ) → ( 1 2 4 5 8 )

Analysis of Bubble sort (Time and Space Complexity)

• Worst case complexity: \(O\left(N^{2}\right)\)
• Best case complexity: O(N) (if the array is already sorted, bubble sort completes in one pass)
• Space complexity: O(1)

Common Bubble Sort Questions

1. Is bubble sort in-place sorting algorithm?

Yes. It doesn’t require extra space and the modifies the source array itself so it qualifies as in-place sorting algorithm.

2. Is bubble sort adaptive?

Yes. In adaptive algorithms, the complexity (running time, performance) changes based on whether or not the input array is sorted. They perform better when the input is sorted. Bubble sort is adaptive because when the input is already sorted, the complexity is O(N) (best case).

4. Is bubble sort divide and conquer?

No. A divide and conquer algorithm continuously breaks down a bigger problem into sub-problems, until they become simple enough to be solved directly. Bubble sort is not a divide and conquer algorithm.

Code Examples

Bubble sort in Java

public static void bubbleSort(int[] arr) {
    int len = arr.length;
    boolean swapped;

    do {
        swapped = false;
        for (int i = 0; i < len - 1; ++i) { // iterate over each element in arr
            for (int j = 0; j < len - i - 1; ++j) {
                if (arr[j + 1] < arr[j]) {
                    int swap = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = swap;
                    swapped = true;
                }
            }
        }
    } while (swapped == true);
}

public static void main(String[] args) {
    int[] arr = {17, 6, 5, 1, 0, 9, 15};
    bubbleSort(arr);

    for (int i = 0; i < len; ++i) {
        System.out.print(arr[i] + " ");
    }
}

Output:

0 1 5 6 9 15 17 

Bubble sort in Python

def bubbleSort(list):
  isSwapped = True

  while(isSwapped):
    isSwapped = False
    for i in range(len(list) - 1):
      if(list[i] > list[i + 1]):
        isSwapped = True
        swap(list, i)

def swap(list, curr_index):
   temp = list[curr_index];
   list[curr_index] = list[curr_index + 1];
   list[curr_index + 1] = temp;

# Test bubble sort
list = [ 19, 1, 9, 3, 10, 13 ]

bubbleSort(list)
print('Sorted array in ascending order:')
print(list)

Other Sorting Algorithms

• Insertion sort
• Selection sort
• Merge sort
• Quick sort
• Shell sort