Insertion and selection sort in PHP

Question

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;
}

• Mike Nakis: 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.
• pguetschow: @MikeNakis Well, that's a point. But i never thought this would be so extreme. But, my code looks fine or is still optimizable?

Answer 1

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(n²) 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 quicksort.

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.

• pguetschow: 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
• pguetschow: 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?
• 200_success: Sure, I see no reason to doubt them.
• pguetschow: Ok, thx, i was a bit suspicious about comparison: insert, as it's in this case n-1