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\$

migrated from softwareengineering.stackexchange.com Mar 14 '17 at 18:02

This question came from our site for professionals, academics, and students working within the systems development life cycle.

  • 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 '17 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 '17 at 18:26
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\$
  • \$\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 '17 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 '17 at 15:17
  • 1
    \$\begingroup\$ Sure, I see no reason to doubt them. \$\endgroup\$ – 200_success Mar 16 '17 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 '17 at 15:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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