CODEWITHSUNDEEP
algorithmsortingbig-obubble-sort
user1505521
user1505521

Reputation: 241

Analysis of a Bubble-sort algorithm

Normally the running time complexity of a buublesort is O(n^2) but the algorithm given below has a while loop and a for loop the for loop depends upon n but the while loop is simply a checker for a boolean value. Can anyone tell me how would i calculate the running time of this algorithm? 

bool done;
done = false;
while ( ! done )
{
done = true;
for ( i = 0 ; i < a.length-1 ; i ++ )
     {
     if ( a[i] > a[i+1] )
     {

// Swap a[i] and a[i+1]

    temp = a[i];
    a[i] = a[i+1];
    a[i+1] = temp;

    done = false;
  }
 }
}

Upvotes: 1

Views: 475

Answers (3)

user1196549
user1196549

Reputation:

This case is much harder than the algorithm with two for loops, as the exact number of iterations of the outer loop does not depend just on N, but also on the particular arrangement of the data.

If the array is initially sorted, there will be no swaps at all and the outer loop will run only once, for a complexity O(N).

If the array is initially sorted in reverse, every comparison induces a swap and the outer loop is executed N times for a total complexity of O(N²).

The general case is much more difficult to assess as it depends on the number of outplaced elements. One can show (by a nontrivial mathematical argument) that for an array in random disorder, the average complexity remains O(N²).

Upvotes: 1

Gangnus
Gangnus

Reputation: 24464

There are several ways how to count the complexity of the algorithm. The most simple and not strict one is to find the worst case and count the number of cycles/iterations for it.

If the source array is arranged vice versa, your code will have to do exactly n^2 comparisons.

All better ways need some serious knowledge of maths: you have to do some strict proof. For example, to prove that the chosen case is really the worst one.

Upvotes: 1

Matt
Matt

Reputation: 15091

Complexity of algorithm is its running time in the worst case (by "case" I mean the whole infinite sequence of input data with increasing length). It's clear that bubblesort needs only O(n) operations "to sort" the arrays which are already sorted. But that doesn't count. There are some arrays (sequences of arrays, actually) which need O(n^2) operations.

P.S. Sometimes it's more interesting whether the algorithm is usually works in O(n) or such. But for bubblesort even "mean expected time" is O(0.5*n^2) which is still the same as O(n^2).

Upvotes: 0

Related Questions