-1
$\begingroup$

So i was trying to write an efficient sorting algorithm and i came up with this method,

Sorting an array in ascending order by flipping (exchanging) 2 adjacent integers not in the correct order until there is no such pair.

The leftmost swappable pair must be swapped first, i.e. the first pair encountered while going from left to right, which is in the opposite (descending order) should be swapped. Then the whole process should be repeated.

and the code i wrote for this is given below

#include<iostream>
using namespace std;

int main()
{
    int n;
    cin>>n;

    int a[n];

    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }


        int j=0;

        //Sorting Logic

        while(j!=n)
        {
            int p=0;
            if(a[j]>a[j+1] && j!=(n-1))
            {
              int t=a[j];
              a[j]=a[j+1];
              a[j+1]=t;
              p=1;
                  }
                  if(p==0)
            j++;
            else
            j=0;

        }



        //Printing the sorted array

        for(int k=0;k<n;k++)
        {   
          cout<<a[k]<<" ";
        }


}

In the best case it will give $O(n)$, but I am unable to figure out the worst case. What will be its worst case complexity? Is it $O(n logn)$ or $O(n^2)$?

$\endgroup$
  • 2
    $\begingroup$ Isn't this just Bubble Sort? $\endgroup$ – Yonatan N Sep 12 at 19:02
  • $\begingroup$ Nope..bubble checks the whole array..here we are checking for the leftmost swappable options $\endgroup$ – HIRAK MONDAL Sep 13 at 9:46
0
$\begingroup$

O(N^2). In the worst case, each iteration before while loop terminates swap n-1 times. So n*(n-1) gives n^2 time complexity.

$\endgroup$
  • 1
    $\begingroup$ This calculation holds in the comparison model. In the time complexity model, there's an amortized linear-time scan before each swap in the case that the initial order is $n/2+1, n/2+2, n/2+3, ... , n, 1, 2, 3, ... n/2$. So the worst case running time is actually cubic. $\endgroup$ – Yonatan N Sep 13 at 19:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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