# What is the Time complexity of this sorting algo?

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

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

• 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. – Yonatan N Sep 13 '19 at 19:45