What is the complexity of this sorting algorithm?

Question

template<class T> void sSort(T *A, int first, int last) 
{
    if(A[first]>A[last])
        swap(A[first],A[last]);

    if(first+1>=last)
    return;
    double  k = floor((last-first+1)/3);


    sSort(A,first,last-k);
    sSort(A,first+k,last);
    sSort(A,first,last-k);
}

I perfectly understood the mergeSort, bubbleSort complexities but i'm so confused in this one. What is the complexity for this algorithm. Can anyone explain?

You could just try running it on a few arrays of different sizes and see how the time compares to the array size... — user541686
– user541686, Commented Nov 11, 2011 at 0:01

user684934 · Accepted Answer · 2011-11-11 00:06:21Z

10

This is the Stooge sort. It's an algorithm constructed to show that amateurs really shouldn't implement their own algorithms without properly analyzing them first. Its running time is approximately O(n^3).

answered Nov 11, 2011 at 0:06

user684934

Sign up to request clarification or add additional context in comments.

1 Comment

LuckySlevin Over a year ago

Thank you, this link help me to reach further documentation.

Aurelio De Rosa · Accepted Answer · 2011-11-11 01:13:10Z

2

It's not too hard to do the calc.

Every time this algorithm do 3 calls to itself splitting into 3 (equal) part the portion of the input of the current step. Note: The first call and the third are the same.
The local complexity is just a O(1) (which means constant) since it will do just a swap, an if and the calculation of k

edited Nov 11, 2011 at 1:13

answered Nov 10, 2011 at 23:50

Aurelio De Rosa

22.2k8 gold badges51 silver badges71 bronze badges

3 Comments

Lars Over a year ago

I am rusty on this kind of thing, but I think it's a bit more involved as the three recursive calls operate on overlapping value ranges.

LuckySlevin Over a year ago

I actually stuck with 3 calls, i can't calculate them, i'm going kinda crazy :)

LuckySlevin Over a year ago

actually algorithm works, but so slowly, you can try to run it :). there aren't any mistyping in the algorithm.

Collectives™ on Stack Overflow

What is the complexity of this sorting algorithm?

2 Answers 2

1 Comment

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related