Why is the temporal complexity of sorting bubbles best equal to O (n)

Question

I determined the temporal complexity of sorting bubbles at best according to the mothod used in ALGORITHMS 2.2. But the answer turned out to be O (n ^ 2).

Here is my conclusion, hope someone can help me find out where it is not:

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)];

at its best casting, the sequence is already positive before sorting. Then t8 may 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)]

Time complexity O (n ^ 2)

Answer 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); } } } 

there is not enough control whether there was any exchange in the inner cycle and the breakdown of the outer cycle if it was not.

This control allows the best case (an already sorted array) to be O (n), since then there are no swaps in the inner loop when it is started for 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; } } } } 

Answer 2

I'm not sure what you think. In general, when you talk about sorting sorting algorithms, you should count the number of comparisons made. The bladder variety is considered as such. In this case, the algorithm you presented is equal to O (n ^ 2).

If you count the number of swaps, then its O (1) or, perhaps, you can even say O (0). However, it is rarely the case to analyze a bubble.

You can, however, improve Bubble very easily to get O (N) at best. For example, entering the swap_was_made flag. If its a lie at the end of the inner for , you can end it. At best, this will complicate O (N) (one inner loop). In the case of a fair uniform distribution, it reduces the expected or average complexity of O (N ^ 2/2) ... But please double check me for this. Maybe I'm wrong. They didn’t do the math here.