1
\$\begingroup\$

I've implemented InsertionSort and SelectionSort in PHP and tested it with an array of 20.000 unique integers.

It took many seconds to complete the insertion selection sorts. For comparison, I saw a Java implementation that only took 3 seconds for both combined. I wanted to ask if my implementations are just bad or if this is a hardware/language based problem.

Here are my methods:

$rand = randomArray(20000);
insertionSort($rand);
selectionSort($rand);


function insertionSort($sort_array){
    $time_start = microtime(true);
    for ($i = 0; $i < count($sort_array)-1; $i++){
      for ($j = $i + 1; $j > 0; $j--)
        {    
          if($sort_array[$j-1] > $sort_array[$j]){
            $temp = $sort_array[$j-1];
            $sort_array[$j-1] = $sort_array[$j];
            $sort_array[$j] = $temp;               
          }         
        } 
    }
    $time_end = microtime(true);
    $time = $time_end - $time_start;
    echo $time;
    return $sort_array;
}

function selectionSort($sort_array) 
{
    $time_start = microtime(true);
    for ($i = 0; $i < count($sort_array) - 1; $i++)
    {
        $min = $i;  
        for ($j = $i + 1; $j < count($sort_array); $j++)
        {
            if ($sort_array[$j] < $sort_array[$min]){
              $min = $j;
        } 
      $temp = $sort_array[$i];
      $sort_array[$i] = $sort_array[$min];
      $sort_array[$min] = $temp;
    }
    $time_end = microtime(true);
    $time = $time_end - $time_start;
    echo $time;
    return $sort_array;
    }
} 

function randomArray($max){
    $random = range(0, $max-1);
    shuffle($random );
    return  $random;
}
\$\endgroup\$
2
  • 1
    \$\begingroup\$ You cannot compare the performance of something written in php, an interpreted, string-based language, with something written in java, a compiled language with machine data types. \$\endgroup\$
    – Mike Nakis
    Mar 14, 2017 at 18:17
  • \$\begingroup\$ @MikeNakis Well, that's a point. But i never thought this would be so extreme. But, my code looks fine or is still optimizable? \$\endgroup\$
    – pguetschow
    Mar 14, 2017 at 18:26

1 Answer 1

1
\$\begingroup\$

One possible inefficiency is that you are copying the array when you call the function. If you pass parameters by reference, then you could avoid allocating and copying the array. See the difference in these two functions that just perform one swap:

function f($a) {
    $swap = $a[0];
    $a[0] = $a[1];
    $a[1] = $swap;
    return $a;
}

function g(&$a) {
    $swap = $a[0];
    $a[0] = $a[1];
    $a[1] = $swap;
}

$xyz = array('x', 'y', 'z');
print_r($xyz);                  # array { [0] => x  [1] => y  [2] => z }
$yxz = f($xyz);
print_r($xyz);                  # array { [0] => x  [1] => y  [2] => z }
print_r($yxz);                  # array { [0] => y  [1] => x  [2] => z }
g($xyz);
print_r($xyz);                  # array { [0] => y  [1] => x  [2] => z }

That aside, there is not that much you can do to optimize your two sorting algorithms. You could try obtaining the length count($sort_array) just once, before the loop, to see if makes any difference.

The important thing to note, though, is that both insertion sort and selection sort are O(n2) algorithms. That means that if you double the size of the array, it will take approximately quadruple the amount of time to complete the sort. If you care about performance when sorting large lists, you don't use insertion sort or selection sort. You pick a more efficient algorithm that tends to work in O(n log n) time, such as .

Comparing performance across languages is not a very useful way to judge the quality of your code. To make a comparison that is at least somewhat fair, try racing against PHP's own array_sort() function.

\$\endgroup\$
4
  • \$\begingroup\$ I initially had the count stored in a variable, after removing this the script became slightly faster. Thanks for your answer, I'd never use this in RL but this was part of an assignment \$\endgroup\$
    – pguetschow
    Mar 15, 2017 at 11:03
  • \$\begingroup\$ Can you take a look at the greaphs on the demo site?: techtreedev.de/BA/algorithm/index.php From left to right: runtime, swaps, comparisons Are those realistic figures? \$\endgroup\$
    – pguetschow
    Mar 16, 2017 at 15:17
  • 1
    \$\begingroup\$ Sure, I see no reason to doubt them. \$\endgroup\$ Mar 16, 2017 at 15:23
  • \$\begingroup\$ Ok, thx, i was a bit suspicious about comparison: insert, as it's in this case n-1 \$\endgroup\$
    – pguetschow
    Mar 16, 2017 at 15:24

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.