1

How would I express the speed of the following sort algorithm? I know bubblesort is n^n (er, I mean n^2...as someone pointed out below). In the following the array decreases each time you call it recursively.

thanks.

$myarray = array("21","4","8","8","1","2","19","21");
mysort($myarray);

function mysort($myarray,$sorted = null){
    if(!isset($sorted)){
        $sorted = array();
    }
    $lowest = $myarray[0];
    $lowindex = 0;
    for($x = 1;$x < count($myarray);$x++){
        if($myarray[$x] < $lowest){
            $lowest = $myarray[$x];
            $lowindex = $x;
        }
    }
    $sorted[] = $lowest;
    array_splice($myarray,$lowindex,1);
    if(count($myarray) > 1){
        echo "calling recursively \n";
        mysort($myarray,$sorted);
    }
    else if(count($myarray) == 1){      
        $sorted[] = $myarray[0];
        $arraystr = print_r($sorted,true);
        echo "sorting finished. Array is $arraystr \n";
        return;
    }
}
Improve this question
3
  • Nothing about bubblesort is n^n. Bubblesort only needs n^2 comparisons. n^n is nonsense because there are only n! permutations; even the naive brute-force "check every permutation, stop when one is sorted) only takes n * n! comparisons.
    – user7043
    Commented Jan 25, 2014 at 13:20
  • Yikes! You are absolutely right. Still, I'm wondering how the speed of the above would be represented. I guess the call to array_splice would have to be taken into consideration.
    – nettie
    Commented Jan 25, 2014 at 13:28
  • @lamphp You mention that you're wondering how to express the speed of the algorithm. I know folks have done a good job of explaining how fast it is, but I guess I wanted to answer the general question a bit. Usually when you look at an algorithm, you typically try to analyze best-case, worst-case, and average case. If you are trying to communicate this to others, you probably want to list all three to get the full context. Worst case is often what's listed, but average case can be very important.
    – J Trana
    Commented Jan 26, 2014 at 6:07

1 Answer 1

Reset to default
1

array_splice is at worst linear time, but let's assume it's constant time (if it's not, one can write that part differently to make it constant time). The algorithm nevertheless has the same asymptotic complexity as Bubblesort:

  1. It finds the smallest element in n comparisons, moves it to the front (leaving n-1 elements to be sorted) and sorts the rest.
  2. It finds the second smallest element in n - 1 comparisons, moves it to the front (leaving n-2 elements to be sorted) and sorts the rest.
  3. It finds the third smallest element in n - 2 comparisons, moves it to the front (leaving n-3 elements to be sorted) and sorts the rest.
  4. ...

In total, there are about n + (n-1) + (n-2) + (n-3) + ... + 1 = 1 + 2 + 3 + ... + n comparisons. This is the triangular number n * (n - 1) / 2, which is in Θ(n^2), the same complexity as Bubblesort.

Not surprisingly, this algorithm is well-known, though it's more commonly done in-place and using a loop instead of recursion. It's called selection sort.

Improve this answer
1
  • I looked at the "selection sort" example and I can see the similarity. I'm transferring sorted elements into a new array and staying at index 0, instead of moving elements to the front as in the example. But in both cases the length of the array decreases on each iteration. Thank you very much for the explanation!
    – nettie
    Commented Jan 25, 2014 at 13:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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