Time Complexity of Bubble Sort Explained with Examples

Bubble Sort is one of the most well-known sorting algorithms in computer science. While it’s not the most efficient method for large datasets, it plays an important role in helping beginners understand the fundamentals of sorting and algorithm design. Its straightforward nature makes it an excellent first algorithm to study, especially when learning about concepts such as iteration, comparison, and algorithmic complexity.

In this guide, we’ll dive into what Bubble Sort is, how it works step-by-step, and how it can be implemented in JavaScript. We’ll then examine the time complexity of Bubble Sort in various scenarios - best case, average case, and worst case - and explore its space complexity. Finally, we’ll compare its performance with other sorting algorithms like Insertion Sort, Selection Sort, Merge Sort, and Quick Sort.

Let’s start by discussing what Bubble Sort is and its key characteristics.

What is Bubble Sort?

Bubble Sort is a straightforward, comparison-based sorting algorithm that is commonly used to introduce beginners to the concept of sorting in computer science. It works by repeatedly iterating through a list, comparing each pair of adjacent values, and swapping them if they are in the wrong order. This process is repeated until the list is completely sorted.

The term ‘Bubble Sort’ comes from the way elements gradually ‘bubble up’ to their correct positions, much like bubbles rising to the surface of water. In each pass through the list, the largest unsorted element moves to its correct position at the end of the array, and this continues until the entire list is sorted.

Key characteristics:

• Comparison-based: Elements are sorted based on comparisons between pairs.
• In-place sorting: It does not require any additional storage space beyond the original array.
• Stable: Equal elements retain their original relative order after sorting.
• Deterministic: For the same input, it always produces the same output.

Next, let’s understand how Bubble Sort works with an example.

How Bubble Sort works

Consider this unsorted array:

[5, 3, 8, 4, 2, 6]

to clipboard
Copy to clipboard

Now, let’s see how Bubble Sort converts this array from unsorted to sorted step-by-step.

First pass:

• Compare 5 and 3: Since 5 > 3, swap them –> [3, 5, 8, 4, 2, 6]
• Compare 5 and 8: Since 5 < 8, no swap is needed –> [3, 5, 8, 4, 2, 6]
• Compare 8 and 4: Since 8 > 4, swap them –> [3, 5, 4, 8, 2, 6]
• Compare 8 and 2: Since 8 > 2, swap them –> [3, 5, 4, 2, 8, 6]
• Compare 8 and 6: Since 8 > 6, swap them –> [3, 5, 4, 2, 6, 8]

The array after the first pass: [3, 5, 4, 2, 6, 8]

Second pass:

• Compare 3 and 5: Since 3 < 5, no swap is needed –> [3, 5, 4, 2, 6, 8]
• Compare 5 and 4: Since 5 > 4, swap them –> [3, 4, 5, 2, 6, 8]
• Compare 5 and 2: Since 5 > 2, swap them –> [3, 4, 2, 5, 6, 8]
• Compare 5 and 6: As 5 < 6, no swap is needed –> [3, 4, 2, 5, 6, 8]

The array after the second pass: [3, 4, 2, 5, 6, 8]

Third pass:

• Compare 3 and 4: Since 3 < 4, no swap is needed –> [3, 4, 2, 5, 6, 8]
• Compare 4 and 2: Since 4 > 2, swap them –> [3, 2, 4, 5, 6, 8]
• Compare 4 and 5: Since 4 < 5, no swap is needed –> [3, 2, 4, 5, 6, 8]

The array after the third pass: [3, 2, 4, 5, 6, 8]

Fourth pass:

• Compare 3 and 2: Since 3 > 2, swap them –> [2, 3, 4, 5, 6, 8]
• Compare 3 and 4: Since 3 < 4, no swap is needed –> [2, 3, 4, 5, 6, 8]

The array after the fourth pass: [2, 3, 4, 5, 6, 8]

Since the array has been sorted, there’s no need for another pass.

Sorted array:

[2, 3, 4, 5, 6, 8]

to clipboard
Copy to clipboard

Here is an image that shows how Bubble Sort has sorted this unsorted array:

Now that we’ve got an idea about how Bubble Sort works, let’s check out the algorithm and pseudocode for it in the next section.

Algorithm and pseudocode for Bubble Sort

Here is the algorithm for Bubble Sort:

• Compare adjacent elements: Starting from the first element, compare it with the next element.
• Swap if necessary: If the first element is greater than the second, swap them.
• Move to the next pair: Move one position to the right and compare the next pair of adjacent elements.
• Repeat the process: Continue doing this for each pair of adjacent elements.
• Finish the pass: After the first pass through the list, the largest element will have ‘bubbled up’ to its correct position.
• Repeat passes: The process repeats for the remaining elements (excluding the already sorted elements) until the entire list is sorted.

Now, let’s have a look at the pseudocode for Bubble Sort:

procedure bubbleSort(array) 
    n = length(array) 
    for i = 0 to n - 1 
        for j = 0 to n - 2 
            if array[j] > array[j + 1] 
                swap(array[j], array[j + 1]) 
end procedure

How it works:

• The outer loop runs from the first to the last element.
• The inner loop compares each pair of adjacent elements.
• If the current element is greater than the next, they are swapped.
• This continues for every pair in every pass, ensuring that by the end of the process, the list is sorted.

With the algorithm and pseudocode covered, let’s learn how to implement Bubble Sort in JavaScript next.

How to implement Bubble Sort in JavaScript

This example demonstrates how we can implement Bubble Sort in JavaScript:

function bubbleSort(arr) { 
  // Get the length of the array 
  let n = arr.length; 

  for (let i = 0; i < n; i++) { 
    for (let j = 0; j < n - 1; j++) { 
      if (arr[j] > arr[j + 1]) { 
        // Swap elements 
        let temp = arr[j]; 
        arr[j] = arr[j + 1]; 
        arr[j + 1] = temp; 
      } 
    } 
  } 

  return arr; 
} 

// Example usage 
console.log(bubbleSort([5, 1, 4, 2, 8])); 

to clipboard
Copy to clipboard

Here, we’ve created a function that implements the Bubble Sort algorithm. In the function, we’ve utilized a temporary variable for swapping the elements during the sorting process. This function takes an array as its only argument, sorts it using Bubble Sort, and returns the sorted array.

Here is the output for the example:

[ 1, 2, 4, 5, 8 ]

to clipboard
Copy to clipboard

In the next section, we’ll analyze the time complexity of Bubble Sort.

Time complexity of Bubble Sort

The time complexity of Bubble Sort is one of the most important aspects to understand when evaluating its performance. Its time complexity can vary depending on the input data’s initial arrangement, and whether or not the algorithm has been optimized to detect early termination. Let’s go through the best, average, and worst-case time complexity of Bubble Sort one by one.

Best-case time complexity:

In the best case, the array is already sorted. If the implementation includes a flag to check whether any swaps were made during a pass, the algorithm can detect this and terminate early. In such a case, only one pass through the array is necessary, and no swaps are performed, resulting in a time complexity of O(n).

Average-case time complexity:

In the average-case scenario, when the array elements are randomly ordered, Bubble Sort performs many comparisons and swaps to sort the list. Each element typically requires multiple passes to reach its correct position. This leads to roughly n(n-1)/2 operations, giving the algorithm a time complexity of O(n²).

Worst-case time complexity:

In the worst case, the array is sorted in reverse order, meaning every pair of adjacent elements must be compared and swapped. The outer loop runs n times, whereas the inner loop performs up to n - i - 1 comparisons in each iteration. As a result, the total number of comparisons approaches n(n-1)/2, resulting in a time complexity of O(n²).

Next, let’s explore the space complexity of Bubble Sort.

Space complexity of Bubble Sort

In the case of Bubble Sort, the space complexity is essential to consider because it helps determine how much additional storage the algorithm needs to process the input array.

In each pass through the array, Bubble Sort only needs a small amount of extra space to store temporary values during swaps. Typically, it only requires a constant amount of space to perform these operations, making its space complexity very efficient. The amount of space needed does not grow with the size of the input array. Therefore, the space complexity is O(1), meaning that it uses constant space regardless of the size of the input.

Bubble Sort vs. other sorting algorithms

Here is a table that compares the space and time complexity of Bubble Sort with other sorting algorithms:

This indicates that Bubble Sort is less efficient than the more advanced algorithms like Merge Sort and Quick Sort, especially for large datasets. However, it is useful for educational purposes and for small datasets where performance is not critical.

Conclusion

Bubble Sort is a basic sorting algorithm that is easy to understand and implement. However, it suffers from poor performance on large or unsorted data due to its O(n²) time complexity. While it’s rarely used in production systems, it’s a great stepping stone for learning how sorting works.

Understanding the time complexity of Bubble Sort helps in making informed choices about when (and when not) to use it. For most real-world applications, more efficient algorithms like Merge Sort or Quick Sort are preferred.

If you want to learn more about Bubble Sort, check out the Learn Data Structures and Algorithms with Python course on Codecademy.

Frequently Asked Questions

1. Is Bubble Sort stable or unstable?

Bubble Sort is a stable sorting algorithm. This means it preserves the relative order of equal elements. For instance, if two elements have the same value and one appears before the other in the original list, they will remain in that order after sorting.

2. What is the formula for Bubble Sort?

The formula for Bubble Sort can be expressed in terms of its best, average, and worst-case time complexity:

• Best case: n - 1
• Average case: (n x (n - 1)) / 2
• Worst case: (n x (n - 1)) / 2

3. Why is Insertion Sort faster than Bubble Sort?

Insertion Sort builds the sorted array one item at a time and only shifts elements when necessary. On the other hand, Bubble Sort repeatedly passes through the entire array, swapping adjacent elements even if only slightly out of place. As a result, Insertion Sort tends to be more efficient on small or nearly sorted datasets.