Где ошибка в реализации QuickSort?

Question

[Dreaded]

Пытаюсь сам реализовать алгоритм сортировки QuickSort. Уже целый час сижу и не могу понять, что я тут делаю не так?

function quicksort(&$array, $first, $last) {
	
	$left = $first;
	$right = $last;
	$pivot = $array[rand($first, $last)];

	do {
		while($array[$left] < $pivot)
			$left++;
		
		while($array[$right] > $pivot)
			$right--;
		
		if ($left <= $right) {
			$temp = $array[$left];
			$array[$left] = $array[$right];
			$array[$right] = $temp;
			$left++;
			$right--;
		}
	}
	while ($left <= $right);

	quicksort($array, $first, $right);
	quicksort($array, $left, $last);
}

Answer 1

[Roman]

У Вас условия не проверяются

quicksort($array, $first, $right);
quicksort($array, $left, $last);

А надо

if ($r > $left) {
//Если условие true, совершаем рекурсию
//Передаем массив, исходное начало и текущий конец
my_sort($array, $left, $r); 
}

if ($l < $right) {
//Если условие true, совершаем рекурсию
//Передаем массив, текущие начало и конец
my_sort($array, $l, $right);
}

https://habr.com/sandbox/33297/

Comments

[Dreaded]

Спасибо за толковую ссылку!