2
$\begingroup$

What is the runtime complexity of the following implementation of Bubblesort (for integers)?

    #define SWAP(a,b)   { int t; t=a; a=b; b=t; }

    void bubble( int a[], int n )
    /* Pre-condition: a contains n items to be sorted */
    {
       int i, j;
      /* Make n passes through the array */
      for(i=0;i<n-1;i++)
      {
     /* From the first element to the end
       of the unsorted section */
        for(j=1;j<(n-i);j++)
        {
        /* If adjacent items are out of order, swap them */
       if( a[j-1]>a[j] ) SWAP(a[j-1],a[j]);
       }
    }
}  
$\endgroup$
  • 6
    $\begingroup$ Bubble sort is a classic algorithm, a quick google will give you the information you're after. $\endgroup$ – Luke Mathieson Oct 7 '12 at 10:18
  • 4
    $\begingroup$ I am tempted to close this question. Blurping code (C, no less!) here and not even taking the time to write down a proper question is not how Stack Exchange should be used. Please include your own effort. You also need to state which operations should be counted. $\endgroup$ – Raphael Oct 7 '12 at 15:48
  • $\begingroup$ See here and here for similar analyses. $\endgroup$ – Raphael Oct 7 '12 at 15:51
  • $\begingroup$ It's been documented and provable that no matter what what kinds of optimization, bubblesort is always O(n^2). $\endgroup$ – CS2016 Oct 11 '17 at 13:56
5
$\begingroup$

The first iteration will do will do $n-1$ comparisons, the next $n-2$, the second $n-3$ and so on. In total $n-1$ iterations are done.

Hence, you need to find the sum of $(n-1)+(n-2) + ... + 1$ which is $((n-1)^2+n-1)/2$ which still is $O(n^2)$. So the optimization does not improve the asymptotic running time.

Note that I edited your algorithm slightly: the outer loop is only iterated $n-1$ times. This is because for each iteration, one more element is put into the right place. Hence after $n-1$ iterations, $n-1$ elements will be in the right place and so element $n$ must also be in the right place.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.