why is the time complexity of bubble sort's be

问题:

I deduced the time complexity of bubble sort in its best case according to the mothod used in book ALGORITHMS 2.2. But the answer turned out to be O(n^2).

Here's my derivation, hope anyone can help me find out where is wrong:

public void bubbleSort(int arr[]) {
for(int i = 0, len = arr.length; i < len - 1; i++) {
    for(int j = 0; j < len - i - 1; j++) {
        if(arr[j + 1] < arr[j])
            swap(arr, j, j + 1);
    }
}

}

Statements                      cost    times
i = 0,len = arr.length          c1          1
i < len - 1                     c2          n
i++                             c3          n - 1
j = 0                           c4          n - 1
j < len - i - 1                 c5          t1(i=0) + t1(i=1) + ... + t1(i = n-2)
j++                             c6          t2(i=0) + t2(i=1) + ... + t2(i = n-2)
arr[j + 1] < arr[j]             c7          t3(i=0) + t3(i=1) + ... + t3(i = n-2)
swap(arr, j, j + 1)             c8          t4(i=0) + t4(i=1) + ... + t4(i = n-2)

T(n) = c1 + c2n + c3(n - 1) + c4(n - 1) + c5t5 + c6t6 + c7t7 + c8t8 = c1 + c2n + c3(n - 1) + c4(n - 1) + c5[t1(i=0) + t1(i=1) + ... + t1(i = n-2)] + c6[t2(i=0) + t2(i=1) + ... + t2(i = n-2)] + c7[t3(i=0) + t3(i=1) + ... + t3(i = n-2)] + c8[t4(i=0) + t4(i=1) + ... + t4(i = n-2)];

in its best cast, the sequence is already positive before sorting. Then t8 sould be 0.

T(n) = c1 + c2n + c3(n - 1) + c4(n - 1) + c5[t1(i=0) + t1(i=1) + ... + t1(i = n-2)] + c6[t2(i=0) + t2(i=1) + ... + t2(i = n-2)] + c7[t3(i=0) + t3(i=1) + ... + t3(i = n-2)]

The time complexity is O(n^2)

回答1:

Your implementation

public void bubbleSort(int arr[]) {
    for(int i = 0, len = arr.length; i < len - 1; i++) {
        for(int j = 0; j < len - i - 1; j++) {
            if(arr[j + 1] < arr[j])
                swap(arr, j, j + 1);
        }
    }
}

lacks the control whether there was any swap in the inner loop, and the breaking out of the outer loop if there wasn't.

That control makes it possible that the best case (an already sorted array) is O(n), since then there are no swaps in the inner loop when it runs the first time.

public void bubbleSort(int arr[]) {
    boolean swapped = true;
    for(int i = 0, len = arr.length; swapped && i < len - 1; i++) {
        swapped = false;
        for(int j = 0; j < len - i - 1; j++) {
            if(arr[j + 1] < arr[j]) {
                swap(arr, j, j + 1);
                swapped = true;
            }
        }
    }
}

回答2:

I am not sure what are you counting. In general, when you are talking about comparison sort algorithms you should count the number of comparisons made. Bubble sort is regarded as such. In this case the algorithm you presented is O(n^2).

If you count the number of swaps its O(1) or maybe even one could say O(0). It is however rare to analyze Bubble sort like that.

You can, however very easily improve Bubble to get O(N) on best case. E.g by introducing a flag swap_was_made. If its false at the end of inner for you can finish. On best case it will cut complexity to O(N) (one inner for loop). In case of fair even distribution it cuts the expected or average complexity to O(N^2/2) ... But please double check me on it I might be wrong. Didn't do the math here.

回答3:

The best case for bubble sort is when the elements are already sorted.

The usual implementation gives O(n^2) time complexity for best, average, worst case.

We can modify the bubble sort by checking if array is sorted or not(a swap would indicate an unsorted array) at every iteration.

As soon as the array is found to be sorted(if no swap occurs) control exits from loops or loop continues to execute till length-1.

And same is true for insertion sort as well!