QuickSort: Не могу понять деталь, когда Pivot меняет свою позицию

Question

Я нашел так много вариантов методов, изучая 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

Answer 1

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

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

стадии 1 : Выберите стержень. (например, случайный индекс или медианная из трех)

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

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

этап 4: Обмен стержень (A[N-1]) с A[r]

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

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

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

Q # 2: давайте поговорим о памяти слишком

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

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

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

Этап 3 Как это Отделение?

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

Answer 2

PHP код Quicksort: (с использованием 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)