计算冒泡排序的时间复杂度

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:

algorithm bubbleSort(A):
    // INPUT
    //   A = input array
    // OUTPUT
    //   Sorted A

    N <- length(A)

    for j <- 1 to N:
        for i <- 0 to N - 1:
            if A[i] > A[i + 1]:
                temp <- A[i]
                A[i] <- A[i + 1]
                A[i + 1] <- temp

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:

algorithm improvedBubbleSort(A):
    // INPUT
    //   A = input array
    // OUTPUT
    //   Sorted A

    N <- length(A)
    indicator <- 1
    j <- 0
    while indicator == 1 and j < N:
        j <- j + 1
        indicator <- 0
        for i <- 1 to N - 1: 
            if A[i] > A[i + 1]:
                temp <- A[i]
                A[i] <- A[i + 1]
                A[i + 1] <- temp
                indicator <- 1

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.

5. Advantages and Disadvantages

Bubble sort is a very simple sorting algorithm to understand and implement. Due to its simplicity, bubble sort is used to introduce sorting algorithms in computer science. Also, it gives a good base for the other popular sorting algorithms. When the input array is almost sorted and we need to swap just a few elements, then the bubble sort is a good option. It’s also a stable sorting algorithm and the polygon filling algorithm uses the bubble sort concept.

The main disadvantage of bubble sort is time complexity. When the input array contains a large number of elements, the efficiency of bubble sort decreases dramatically and the average time increases quadratically. The performance of bubble sort in the modern CPU hardware is very poor. Though the running time of bubble sort is asymptotically equivalent to other popular sorting algorithms like insertion sort, bubble sort performs a very high number of swaps between elements.

6. Conclusion

In this tutorial, we’ve discussed bubble sort. We’ve presented a standard version and an improved version of the bubble sort algorithm.

Furthermore, we’ve shown a detailed analysis of the time complexity for both the versions.