Bubble sort and modification

Increasing order:

for(i=0;i<n;i++)

  {

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

       if(a[j]>a[j+1])

           swap(&a[j],&a[j+1]);

   }

Here n-i-1 in second loop because after one iteration last element is in its correct place.No need to check that if condition for that

after one iteration leave last one

after two leave two so n-i-1       

 O(n^2) for all cases Time complexity

O(1) for space complexity

But think even if u give a sorted array this algo checks again all condition with O(n^2) even in some times the array may be sorted in third iteration but because of algo  it has to run may be 10 times which makes the complexity

Modification:

So if we make some modification to find after loop that if swapping doesn't happen then we can come out of loop for that

for(i=0;i<n;i++)

  {

        flag=0;

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

       if(a[j]>a[j+1])

          {

           swap(&a[j],&a[j+1]);

            flag=1;

           }

         if(flag==0)

              break;

   }

for this if input array is already sorted then it will have only O(n) complexity.

O(n) if input is already sorted, but even after some iterations before condition fails if it comes out of loop then  O(n^2).