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

using namespace std;

int main()
    int n;

    int a[n];

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

        int j=0;

        //Sorting Logic

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


        //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)$?

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

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.

| cite | improve this answer | |
  • 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 '19 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.