Bubble sort in PHP

Question

Does this code show proper implementation of bubble sort algorithm? If not, why? Can this code further be improved?

<?php

function swap($arr,$p1,$p2)
{
    $temp = $arr[$p2];
    $arr[$p2] = $arr[$p1];
    $arr[$p1] = $temp;
    return $arr;
}

function bubble($arr)
{
    $count = count($arr);
    for ($j = 1; $j < $count; $j++)
    {
        for ($i=1; $i < $count-$j+1; $i++)
        {
            if ($arr[$i-1] > $arr[$i])
            {
                $arr = swap($arr, $i-1, $i);
            }
        }
    }
    return $arr;
}

$in = range(1,20); 
shuffle($in);
?>
<pre>
<?php
    print_r($in);
    print_r(bubble($in));
?>

Answer 1

Instead of swap returning the array, it will be more efficient to pass the array by reference:

function swap(&$arr,$p1,$p2)
{
    $temp = $arr[$p2];
    $arr[$p2] = $arr[$p1];
    $arr[$p1] = $temp;
}

And call it like this, without reassigning to $arr:

swap($arr, $i-1, $i);

This way you avoid unnecessary copying.

Answer 2

You could get rid of many array lookups, and array copying, to make it more efficient, like this:

function bubble($arr)
{
    $count = count($arr);
    for ($j = 1; $j < $count; $j++)
    {
        $v1 = $arr[0];
        for ($i=1; $i < $count-$j+1; $i++)
        {
            $v2 = $arr[$i];
            if ($v1 > $v2)
            {
                $arr[$i-1] = $v2;
                $arr[$i]   = $v1;
            }
            $v1 = $v2;
        }
    }
    return $arr;
}

I've tested your code against this and it is 99.9% faster. It is also almost three times as fast as the answer by janos. Why?

Function calls and call stack

Each time a function is called the function parameters are pushed onto the call stack and before the code within the function can be executed these parameters have to be retrieved from the call stack. This takes time. (see: https://en.wikipedia.org/wiki/Call_stack#Description) By not using an extra swap() function we save the time otherwise spent manipulating the call stack.

Array manipulation

Manipulating an array value also takes more time than changing the value of a simple variable. This is because before the array value can be changed it first needs to be located by using a key (also called 'index'). We should therefore try to minimize the amount of array manipulations.

In my code I have done this by storing array values in the local variables $v1 and $v2. There are two array lookups, of which only one is in the inner loop, and two array assignments, which are only used when actually needed.