How many comparisons of array items do the following loops c

How many comparisons of array items do the following loops contain?

for(j=1; j<=n-1; ++j)

{

i=j+1;

do

{

if(theArray[i] < the Array[j])

swap(theArray[i], theArray[j});

++i;

} while(i<=n);

}

please write step by step on how to solve this problem with neat handwritting please? thank you

Solution

for(j=1; j<=n-1; ++j)
{
   i=j+1;

   do
   {
       if(theArray[i] < the Array[j])
           swap(theArray[i], theArray[j]);
       ++i;
   }while(i<=n);
}

Hi, THis is Bubble Sort: sorting the number in non-increasing order
We realize that every number needs to be eventually swapped with every number after it that\'s less than it, sooner or later. Thus, the total number of swaps for a given number is the total number of numbers after it which are less than it.

Number of Comparison:
Sum of 1 + 2 + 3 + 4 + .... + n = n * (n + 1)/2

However, this is still O(n^2) time.