Почему второй элемент массива php по ссылке дает неверные результаты?

Question

У меня есть эта простая функция быстрой сортировки (я получил ее от дяди "G")

function quicksort( &$list, $l , $r ) {

$i = $l;
$j = $r;

$tmp = $list[(int)( ($l+$r)/2 )];

do {
    while( $list[$i] < $tmp )
        $i++;

    while( $tmp < $list[$j] )
        $j--;

    if( $i <= $j ) {

        $w = $list[$i];
        $list[$i] = $list[$j];
        $list[$j] = $w;

        //_swp($list[$i],$list[$j]);

        $i++;
        $j--;
    }
}while( $i <= $j );


if( $l < $j )
    quicksort($list, $l, $j);


if( $i < $r )
    quicksort($list, $i, $r);

return $list;
}

И у меня есть эта маленькая функция для обмена двумя переменными.

function _swp(&$a,&$b){
    $a=$a+$b;
    $b=$a-$b;
    $a=$a-$b;
}

Как получилосьЯ не могу использовать _swp ($ a, $ b) в функции quicksort вместо этих строк?

$w = $list[$i];
$list[$i] = $list[$j];
$list[$j] = $w;

Если я закомментирую эти 3 строки кода и введу вызов функции _swp, я получу ошибкурезультаты ...
Пожалуйста, объясните.
С уважением

Answer 1

неожиданное поведение, вероятно, является "случайным" вхождением нулей в отсортированный список.Это происходит потому, что при обмене существует особый случай:

if( $i <= $j ) {
    // swapping here using references!
    _swp($list[$i],$list[$j]);
    $i++;
    $j--;
}

Проблема находится непосредственно в условии самой замены: if $i==$j тогда есть две ссылки на одну и ту же переменную.Таким образом, вызов _swp($list[$i],$list[$j]); сначала добавит обе переменные $a = $a + $b.Учитывая, что $ a и $ b фактически обращаются к одному и тому же содержимому переменной, $ a и $ b будут иметь одинаковое значение.На следующем шаге $b = $a - $b будет равен нулю, так как $ a равно $ b.Третья операция оставляет результат равным 0.

Простым решением для этого является вставка еще одного условия:

if( $i <= $j ) {
    // ensure $i to be truly smaller than $j
    if( $i < $j ) {
        _swp($list[$i],$list[$j]);
    }
    $i++;
    $j--;
}

Надеюсь, это поможет вам.Ура, Фабиан