# Complexity of optimized bubblesort [closed]

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

• Bubble sort is a classic algorithm, a quick google will give you the information you're after. Oct 7, 2012 at 10:18
• 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.
– Raphael
Oct 7, 2012 at 15:48
• See here and here for similar analyses.
– Raphael
Oct 7, 2012 at 15:51
• It's been documented and provable that no matter what what kinds of optimization, bubblesort is always O(n^2). Oct 11, 2017 at 13:56

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.