быстрая сортировка: поток управления в быстрой сортировке - PullRequest
Новая
       14

быстрая сортировка: поток управления в быстрой сортировке

1 голос
/ 18 октября 2011

В том, что мне кажется обычной реализацией быстрой сортировки, программа состоит из подпрограммы разбиения и двух рекурсивных вызовов для быстрой сортировки этих (двух) разделов.

Таким образом, поток управления, в самом быстром и псевдо-эссе псевдокода, выглядит примерно так: 

quicksort[list, some parameters]
.
.
.
q=partition[some other parameters]
quicksort[1,q]
quicksort[q+1,length[list]]
.
.
.
End

q - это "пивот" после разбиения. Этот второй вызов быстрой сортировки - тот, который будет быстро сортировать вторую часть списка, также использует q. Это то, что я не понимаю. Если «поток управления» сначала проходит первую быструю сортировку, q будет обновляться. Как тот же q будет работать во второй быстрой сортировке, когда приходит время выполнить вторые части всех этих разделов?

Я думаю, мое недоразумение проистекает из ограничений псевдокода. Есть детали, которые, вероятно, были опущены при выражении этой реализации алгоритма быстрой сортировки в псевдокоде.

Редактировать 1 Это похоже на мою проблему: 

For[i = 1, i < 5, i = i + 1, Print[i]]

В первый раз мы получим i = 1, правда, i = 2, 1 . Даже если i был обновлен до 2, i по-прежнему равен 1 в теле (то есть Print [i] = 1). Этот «поток контроля» - это то, что я не понимаю. Где хранится значение i = 1, когда оно увеличивается до 2 и до того, как оно попадет в тело?

Редактировать 2

В качестве примера того, что я пытаюсь получить, я вставляю это здесь. Это отсюда. 

Partition(A,p,r)
x=A[r]
i=p+1
j=r+1
while TRUE
    repeat j=j-1
       until A[j]<=x
    repeat i=i+1
       until A[i]>=x
    if i<j
       then exchange A[i] with A[j]
       else return j

Quicksort(A,1,length[A])

Quicksort(A,p,r)
if p<r
    then q=Partition(A,p,r)
        Quicksort(A,p,q)
        Quicksort(A,q+1,r)

Другой пример можно найти здесь.

Где или когда в этих алгоритмах q помещается в стек?

Ответы [ 3 ]

1 голос
/ 18 октября 2011

q не обновляется.Поворот остается на своем месте.В каждой итерации быстрой сортировки единственный элемент, который гарантированно находится на своем правильном месте, - это точка.

Также обратите внимание, что q, который "изменился" во времярекурсивный вызов на самом деле НЕ изменяется, поскольку это другая переменная, хранящаяся в другой области, это верно, потому что q является локальной переменной функции и генерируется для каждого вызова.

РЕДАКТИРОВАТЬ: [ответ на редактирование вопроса]
В быстрой сортировке алгоритм фактически генерирует число q с, которые хранятся в стеке .Каждая переменная «жива» только для своей собственной функции и доступна [в этом примере] только из нее.Когда функция завершается, локальная переменная освобождается автоматически, так что на самом деле у вас нет только одного стержня, у вас фактически есть число стержней , по одному на каждый рекурсивный шаг.

0 голосов
/ 24 сентября 2012

Код раздела выбирает некоторое значение из массива (например, значение в средней точке массива ... ваш пример кода выбирает последний элемент) - это стержень. Затем он помещает все значения <= pivot слева и все значения> = pivot справа и затем сохраняет pivot в одном оставшемся слоте между ними. В этот момент стержень обязательно находится в правильном слоте, q. Затем алгоритм сортирует раздел [p, q) и раздел [q + 1, r), которые не пересекаются, но покрывают все A, кроме q, что приводит к сортировке всего массива.

0 голосов
/ 19 октября 2011

Оказывается, Quicksort требует дополнительной памяти, чтобы функционировать точно для выполнения упомянутой вами поддержки. Возможно, следующая (псевдокодовая) итерационная версия алгоритма может прояснить ситуацию: 

quicksort(array, begin, end) =
    intervals_to_sort = {(begin, end)}; //a set
    while there are intervals to sort:
        (begin, end) = remove an interval from intervals_to_sort
        if length of (begin, end) >= 2:
            q = partition(array, begin, end)
            add (begin, q) to intervals_to_sort
            add (q+1, end) to intervals_to_sort

Вы можете заметить, что теперь сортируемые интервалы явно хранятся в структуре данных (обычно это просто массив, вставка и удаление в конце, как в стеке), поэтому нет риска «забыть» о старые интервалы.

Что может вас смущать, так это то, что наиболее распространенное описание быстрой сортировки является рекурсивным, поэтому переменная q появляется несколько раз. Ответ заключается в том, что каждый раз, когда вызывается функция, она создает новую группу локальных переменных, чтобы она не касалась старых. В конце концов, явный стек из этого предыдущего императивного примера заканчивается реализацией в виде неявного стека с переменными функции.

(Интересное примечание: в некоторых ранних языках программирования не реализовывались такие аккуратные локальные переменные, и Quicksort был фактически впервые описан с использованием итерационной версии с явным стеком. Только позднее было видно, как Quicksort может быть элегантно описывается как рекурсивный алгоритм в Algol.)

Что касается детали после вашего редактирования, то i = 1 забывается, так как присваивание будет деструктивно обновлять переменную.

...