CODEWITHSUNDEEP
windowssortingtime-complexityselection-sortstable-sort
Dhanush Kannan
Dhanush Kannan

Reputation: 11

What is the time complexity of Stable Selection Sort algorithm?

static void stableSelectionSort(int[] a, int n)
{
    for (int i = 0; i < n - 1; i++)
    {
        int min = i;
        for (int j = i + 1; j < n; j++)
            if (a[min] > a[j])
                min = j;

        // Move minimum element at current i.
        int key = a[min];
        while (min > i)
        {
            a[min] = a[min - 1];
            min--;
        }
         
        a[i] = key;
    }
}

What will be the time complexity of Stable selection sort algo? Will it be same as selection sort?

Upvotes: 0

Views: 64

Answers (1)

arpit dixit
arpit dixit

Reputation: 42

So the outer loop runns n-1 times.The first inner loop from i to n, that is for first time it runs n-1 time then n-2 then n-3 ... 1 . Now for the second loop suppose if all the elements are same then each time the loop would be running from i to 0 , adding both first and second loop the inside loops would be running for n times ,so the worst time complexity would reach n^2

Upvotes: 0

Related Questions