Здравствуйте, изучаю алгоритмы по книге "Грокаем алгоритмы", пишу на 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 копейки, если ты не разбираешься в технологии и, видимо, алгоритме сортировки. Не помню, чтобы тостер назывался "Клуб мастодонтов программирования, которые даже не считают нужным отвечать на мелкие и новичковые вопросы".