2
\$\begingroup\$

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));
?>
\$\endgroup\$
7
\$\begingroup\$

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.

\$\endgroup\$
6
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ I was trying to implement algorithm, so \$\endgroup\$ – Viral Feb 27 '15 at 9:39
  • \$\begingroup\$ You could get rid of many array lookups, and array copying - by doing what? This review is not very helpful (yet). \$\endgroup\$ – t3chb0t Apr 23 '18 at 7:31
  • \$\begingroup\$ @t3chb0t: Looks to me like my explanation is the same as in the accepted answer: It's more efficient. The code itself shows you what the changes are. Read the question and the code. If you actually tested the code you'll find it to be 99,9% faster than the code in the question, underlining my point about efficiency. It's also almost three times as fast as the accepted answer, but Viral clearly didn't even try it. \$\endgroup\$ – KIKO Software Apr 23 '18 at 8:11
  • \$\begingroup\$ Maybe... but Code Review is not only about posting the most efficient/fastest version. It's also about learing and explaining how and why the code is faster so be so kind please and explain what you did that made this code as fast as the wind. \$\endgroup\$ – t3chb0t Apr 23 '18 at 8:24
  • 1
    \$\begingroup\$ I've added an explanation. \$\endgroup\$ – KIKO Software Apr 23 '18 at 9:04

protected by Jamal Jun 13 at 2:57

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

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