@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 копейки, если ты не разбираешься в технологии и, видимо, алгоритме сортировки. Не помню, чтобы тостер назывался "Клуб мастодонтов программирования, которые даже не считают нужным отвечать на мелкие и новичковые вопросы".
  • Вопрос задан
  • 155 просмотров
Решения вопроса 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));
}
Ответ написан
Комментировать
Пригласить эксперта
Ответы на вопрос 1
nokimaro
@nokimaro
Меня невозможно остановить, если я смогу начать.
Все ломается

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

$elem = [$array[rand(0, count($array) - 1)]];
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Похожие вопросы