# 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. Commented 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. Commented Oct 7, 2012 at 15:48
• See here and here for similar analyses. Commented 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). Commented 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.