Почему моя быстрая сортировка работает неочевидно?

Question

[gigisarri98]

Здравствуйте, изучаю алгоритмы по книге "Грокаем алгоритмы", пишу на PHP, сейчас дошел до быстрой сортировки. Как мне кажется, я более-менее понимаю принцип работы алгоритма, однако, я не могу понять в чем дело. Вот рабочий код:

function testsort(array $array) {
    if (count($array) < 2) {
        return $array;
    }

    $elem = [$array[0]];
    $left = [];
    $right = [];

    for ($i = 1; $i < count($array); $i++) {
        if ($array[$i] <= $elem[0]) {
            $left[] = $array[$i];
        } else {
            $right[] = $array[$i];
        }
    }

    return array_merge(testsort($left), $elem, testsort($right));
}

Окей, когда опорный элемент - первый элемент массива, я понял, но стоит мне сделать следующее:
$elem = [$array[rand(0, count($array) - 1)]];
Все ломается. Вот один из вариантов вывода при сортировке массива [2,4,6,1,5,3]:

array (size=6)
0 => int 3
1 => int 3
2 => int 3
3 => int 4
4 => int 5
5 => int 5

Аналогичная ситуация, когда я, например, опорным беру последний элемент массива.

Еще мне непонятно, почему цикл должен начинаться с единицы, изначально я пытался делать с нуля, но случалось переполнение стека, и прогуглив, я увидел аналогичное решение, но с единицей вместо нуля.

Объясните, пожалуйста, почему так происходит и как это исправлять. Я не смог найти решение этой проблемы в интернете, более того, даже в этой книге спустя пару страниц рекомендуют брать за опорный элемент элемент посередине, но я не могу его взять, потому что цикл ломается при любой цифре кроме нуля. Заранее спасибо!

UPD: правильный ответ ниже

Маленький p.s.
Мне интересно, на кой черт сидеть в таких достаточно каверзных темах, как алгоритмы (да еще и в топике, где явно указан язык), если ты не можешь сказать по делу ничего полезного, но делаешь это с очень умным видом? Мне непонятно желание везде вставить свои 3 копейки, если ты не разбираешься в технологии и, видимо, алгоритме сортировки. Не помню, чтобы тостер назывался "Клуб мастодонтов программирования, которые даже не считают нужным отвечать на мелкие и новичковые вопросы".

Comments

[gigisarri98]

Igor Borisov, а разве существуют разные алгоритмы на Пайтоне и ПиЭйчПи?

[gigisarri98]

Igor Borisov, извините, но разве я писал, что я слепо скопировал Пайтоновский код?
Вот пример из книги, сравните:

Ключевая идея одна и та же, но синтаксис и какие-то особенности языка свои (в данном случае выделяется цикл). Какое это имеет отношение к быстрой сортировке как идее?

[gigisarri98]

Igor Borisov,

языки отличаются не только синтаксисом (неожиданно). Особенностей больше, чем вы ожидаете. А то так бы все трансляторы понаписали из Python в PHP и учили бы один язык вместо кучи других.

Понимаю о чем Вы, замечание уместно, спасибо. Но предоставленные Вами ссылки (как минимум две последние) делают то же самое, что и мой код.
Идея о том, что цикл начинается с единицы, как раз и взята с этих ссылок. Более того, наш код получился чуть ли не идентичным.

Потому проблема остается: если опорный элемент - нулевой элемент массива, то всё ок, иначе - все ломается.
Я заменил рандомайзер на средний элемент массива, результат - в комментарии под первым ответом.

В последней ссылке есть комментарий над строкой с началом цикла:

// Сравнить среднее значение массива, обратить внимание на значение $ i, начиная с 1 (или $ i = 0; $ i <$ count-1)

Я сделал аналогично (к слову, не понимая, какой смысл в этой манипуляции, и получил такой вывод:

array (size=6)
0 => int 2
1 => int 4
2 => int 5
3 => int 5
4 => int 5
5 => int 6

[gigisarri98]

Igor Borisov, пожалуйста, если Вы знаете ответ, напишите его, я не могу понять Ваших намёков, потому что я всего-лишь новичок.

[gigisarri98]

Igor Borisov, зачем же вы тогда пишите и даёте советы, если сами не разбираетесь?

Answer 1

[gigisarri98]

Решалось все элементарно, как я понял, цикл доходил до итерации, где оставалось 2-3 элемента в массиве и ломался, потому что в цикл был включен перебор и опорного элемента. В итоге, просто явно указав циклу, что надо идти дальше, когда он доходит до пивота, проблема решилась и всё сортируется. Чтобы он не отсеивал одинаковые, я создал переменную $temp, которая служит маркером, был ли этот элемент уже перебран.

function testsort(array $array) {
    if (count($array) < 2) {
        return $array;
    }
    
    $elem = [$array[(int)count($array) / 2]];

    $left = [];
    $right = [];
    $temp = '';

    for ($i = 0; $i < count($array); $i++) {
        if ($array[$i] < $elem[0]) {
            $left[] = $array[$i];
        }

        if ($array[$i] > $elem[0]) {
            $right[] = $array[$i];
        }

        if ($array[$i] == $elem[0]) {
            if ($temp) {
                $left[] = $array[$i];
            } else {
                $temp = $elem[0];
                continue;
            }
        }
    }

    return array_merge(testsort($left), $elem, testsort($right));
}

Answer 2

[nokimaro]

Все ломается

потому что при рекурсивном вызове функции rand() выдаёт разное значение и опорный элемент прыгает

$elem = [$array[rand(0, count($array) - 1)]];

Comments

[gigisarri98]

Спасибо за наводку.
Смотрите, беру не rand(), а элемент посередине:
Допустим, я поменял исходный массив на этот: [2,4,6,5,1,3].
И меняю эту строчку на следующую, делая опорным элемент посередине:
$elem = [$array[round(count($array) / 2)]];
Вывод следующий:

array (size=6)
0 => int 1
1 => int 1
2 => int 3
3 => int 3
4 => int 5
5 => int 6

Я могу сделать вывод, что сортирует он правильно, только вот ошибка возникает в цикле, который, начинается не с нуля, а с единицы, раз - что мне и непонятно...