How to calculate bubble sort time

Question

I tried to understand the data structure and another algorithm, then I got confused to measure the complexity of the Bubble sort time.

for (c = 0; c < ( n - 1 ); c++) { for (d = 0; d < n - c - 1; d++) { if (array[d] > array[d+1]) /* For descending order use < */ { swap = array[d]; array[d] = array[d+1]; array[d+1] = swap; } } } 

Now every Big O talks about the best case O (n), the case Avg (n2) and the worst case (n2). But when I see the code found in the inner loop of the first phase, run n times, and then in the second phase n - 1, n - 2, etc. This means that at each iteration its value decreases. For example, if I have [] = {4, 2, 9, 5, 3, 6, 11}, then the total number of comparisons will be -

 1st Phase - 7 time 2nd phase - 6 time 3rd Phase - 5 time 4th Phase - 4 time 5th Phase - 3 time 6th Phase - 2 time 7th Phase - 1 time 

so when I calculate the time it looks like = (7 + 6 + 5 + 4 + 3 + 2 + 1) + 7 = 35, but the worst time complexity is n2 according to the document.

so can someone tell me how to calculate the correct value.

Answer 1

Go through the cases for Big O for Bubble Sort

Case 1) O (n) (Best case) This time complexity can occur if the array is already sorted, which means that no swap has occurred and only 1 iteration of n elements

Case 2) O (n ^ 2) (worst case) Worst case is if the array is already sorted, but in descending order. This means that in the first iteration he will have to look at n elements, after which he will look like n - 1 elements (since the largest integer is at the end), etc. Etc. Up to 1 comparison. Big-O = n + n - 1 + n - 2 ... + 1 = (n * (n + 1)) / 2 = O (n ^ 2)

In your example, it cannot consider these many elements in each phase, since the array is not in descending order.

Answer 2

So, you noticed that the total number of comparisons performed is n + (n - 1) + ... + 2 + 1. This sum is n * (n + 1) / 2 (see Triangular numbers ), which is 0 , 5 n ^ 2 + 0.5 n, which is obviously O (n ^ 2).

Answer 3

compares two items. therefore, in the comparison of the 1st phase - n-1. i.e. 6 Phase 2 Comparison - n-2. those. 5 and so on to 1. and, therefore, sum = n (n-1) / 2 ie O (n ^ 2).

if there is an error that you can fix .....

Answer 4

O(n^2) = n(n-1)/2 is correct.

As in the example above of 5 elements.

 5(5-1)/2 == 10. 5(5+1)/2 != 10. 

Answer 5

The worst case explanation is here:

 elements = raw_input("enter comma separated elements : ") elements = elements.split(',') elements = map(int, elements) length = len(elements) for i in xrange(length - 1): print "outer pass : ", i for j in xrange(length - i - 1): print "inner pass : ", j if elements[j] > elements[j + 1]: elements[j + 1], elements[j] = elements[j], elements[j + 1] print "elements : ", elements print elements 

Output:

enter items separated by commas: 5,4,3,2,1

Outside passage: 0

inner passage: 0

: [4, 5, 3, 2, 1]

inner passage: 1

: [4, 3, 5, 2, 1]

inner passage: 2

: [4, 3, 2, 5, 1]

inner passage: 3

: [4, 3, 2, 1, 5]

Outside passage: 1

inner passage: 0

: [3, 4, 2, 1, 5]

inner passage: 1

: [3, 2, 4, 1, 5]

inner passage: 2

: [3, 2, 1, 4, 5]

Outer passage: 2

inner passage: 0

: [2, 3, 1, 4, 5]

inner passage: 1

: [2, 1, 3, 4, 5]

Outer passage: 3

inner passage: 0

: [1, 2, 3, 4, 5]

[1, 2, 3, 4, 5]

Thus, the first iteration of all n elements is checked; it will scan n - 1 elements in the next iteration. So for all the elements.

n + n - 1 + n - 2 ... + 1 = (n * (n + 1)) / 2 = O (n ^ 2)

Answer 6

For n numbers of numbers, the total number of comparisons performed will be (n - 1) + ... + 2 + 1. This sum is (n-1) * n / 2 (see Triangular numbers), which is 0.5 n ^ 2 - 0.5 n, i.e. O (n ^ 2)