Быстрая сортировка: не может понять часть, когда Pivot меняет свою позицию

Question

Быстрая сортировка: не может понять часть, когда Pivot меняет свою позицию

Я нашел так много вариантов методов, изучая Quicksort онлайн.

Каждый раз, когда это меня смущало на этапе «Замена / замена шарнирной позиции» после Левый / правый указатели скрещены.

Вопрос: Заменяйте шарнир на левую / правую позицию указателя после каждого раунда. это вопрос.

извините, я не могу найти подходящих примеров, так как я не могу сделать это, чтобы удовлетворить мой вопрос. но, пожалуйста, если у кого-то есть лучший пример, а также Код PHP из этого?

Пример: [81,70,97,38,63,21,85,68,76,9,57,36,55,79,74,85,16,61,77,49,24] принять поворот: 57

можете взять этот пример, если хотите:
https://ece.uwaterloo.ca/~cmoreno/ece250/quick-sort-complete-example.pdf

0

algorithm php pivot quicksort sorting

Решение

Другие решения

PHP-код для быстрой сортировки: (используя Схема разбиения Lomuto Я думаю)

<?php$unsorted = array(43,21,2,1,9,24,2,99,23,8,7,114,92,5);

function quick_sort($array)
{
// find array size
$length = count($array);

// base case test, if array of length 0 then just return array to caller
if($length <= 1){
return $array;
}
else{

// select an item to act as our pivot point, since list is unsorted first position is easiest
$pivot = $array[0];

// declare our two arrays to act as partitions
$left = $right = array();

// loop and compare each item in the array to the pivot value, place item in appropriate partition
for($i = 1; $i < count($array); $i++)
{
if($array[$i] < $pivot){
$left[] = $array[$i];
}
else{
$right[] = $array[$i];
}
}

// use recursion to now sort the left and right lists
return array_merge(quick_sort($left), array($pivot), quick_sort($right));
}
}

$sorted = quick_sort($unsorted);
print_r($sorted);

?>

//RESULT: Array ( [0] => 1 [1] => 2 [2] => 2 [3] => 5 [4] => 7 [5] => 8 [6] => 9 [7] => 21 [8] => 23 [9] => 24 [10] => 43 [11] => 92 [12] => 99 [13] => 114 )

0

Источник

Accepted Answer

Пытаюсь помочь вам сделать вопрос более понятным

Рассмотрим такой сценарий для массива с N элементами:

Этап 1: Выберите опору. (например, случайный индекс или медиана-три)

Стадия 2: Поставить точку поворота в какую-то позицию. Например, обменять значение по сводному индексу с последним элементом. Pivot сейчас находится в A[N-1]

этап 3: разделить все элементы, кроме точки поворота (последняя позиция) — меньшие элементы находятся в A[0]..A[l], большие элементы находятся в A[r]..A[N-2]

4 этап: обменный пункт (A[N-1]) с A[r]

Какой этап не понятен?

Вопрос № 1: является ли обязательным этап 2 для установки разворота, меняя его на первую / последнюю позицию? потому что я не нашел это в каждом примере. где-то там, где он остается, и после 1-го раунда меняет свое положение указателем вверх / вниз.

Если вы используете первый или последний элемент в качестве сводного, вам не нужно менять его, иначе обмен обязателен. Обратите внимание, что pivot = first — это самый простой метод для выбора pivot, но вероятность наихудшего случая слишком высока — для (почти) отсортированных массивов]

Q # 2: давайте поговорим о памяти тоже

QuickSort не требует дополнительной памяти для нового массива, он работает на месте. Рекурсивная реализация занимает некоторую память в стеке (неявно).

замена точки поворота на A [r] означает правую (нижнюю) позицию указателя после 1-го раунда, верно?

Да, это позиция указателя вниз при пересечении. Примечание — замена указателем вниз, когда точка разворота находится в конце, но замена указателем вверх, когда точка поворота находится в начале.

Стадия 3 Как это отделилось?

Использование схемы разбиения Wiki. Рассмотрим раздел Хоара — его проще понять.

1