Прогрессия алгоритма быстрой сортировки с равными элементами

Я работаю над назначением алгоритмов, которое требует, чтобы я показывал ход алгоритма быстрой сортировки с массивом равных элементов (1 (a), 1 (b), 1 (c) и т. д.), причем ось является последним элементом массива. Рекурсивная часть алгоритма - это то, что меня смущает. До сих пор я прогрессию:Прогрессия алгоритма быстрой сортировки с равными элементами

1(a) 1(b) 1(c) 1(d) [1(e)] 
1(a) | 1(b) 1(c) 1(d) 1(e) 
1(a) 1(b) | 1(c) 1(d) 1(e) 
1(a) 1(b) 1(c) | 1(d) 1(e) 
1(a) 1(b) 1(c) 1(d) | 1(e)

После этого поворота стал бы 1 (г) Я думаю, и прогрессия будет таким же, как описано выше, за исключением одного меньше обмена. Я смущен тем, как работают левые и правые рекурсивные вызовы. Могут ли элементы в «правой» части массива обмениваться с самими собой? В какой момент этот алгоритм остановится?

Вот псевдокод:

QS(A, p, r): 
if p < r 
    q = PARTITION(A, p, r) 
    QS(A, p, q - 1) 
    QS(A, q + 1, r) 

PARTITION(A, p, r): 
x = A[r] 
i = p - 1 
for j = p to r - 1 
    if A[j] <= x 
     i = i + 1 
     exchange A[i] with A[j] 
exchange A[i + 1] with A[r] 
return i + 1

р является первым элементом массива и г является последним элементом.

Благодарим за помощь.

источник

2016-03-25 tfreiner

ваш вопрос непонятный. вы не показываете псевдокод. –

Моя ошибка. Просто добавил! – tfreiner

Вот некоторые объяснения, которые могут помочь: [быстрый сортировать с повторяющимися элементами] (http://stackoverflow.com/questions/13339227/quick-sort-algorithm-improvement-if-more-duplicate-keys). – Crocode

Второй вызов, QS(A, q + 1, r), в вашем случае всегда будет не оп, потому что q всегда будут равны r, поэтому вызов становится QS(A, r+1, r), который по if p < r охраннику становится не оп (p < r не всегда будет ложный).

Итак, если ваш массив проиндексирован 1, 2, ..., 5; первое значение q равно 5, поэтому его первый рекурсивный вызов равен QS(A,1,4), а второй - QS(A,6,5) (нет-op).

То же самое будет происходить за QS(A,1,4) - его q будет 4, а два вызова - QS(A,1,3) и QS(A,5,4).

QA(A,1,5) 
    PARTITION(A,1,5) -> 5 
    QS(A,1,4) 
     PARTITION(A,1,4) -> 4 
     QS(A,1,3) 
      PARTITION(A,1,3) -> 3 
      QS(A,1,2) 
       PARTITION(A,1,2) -> 2 
        QS(A,1,1) 
        QS(A,3,2) 
      QS(A,4,3) 
     QS(A,5,4) 
    QS(A,6,5)

Интересный способ кодирования partition, никогда не видел, это было сделано таким образом. Я бы использовал < вместо <= там, чтобы не менять обычные элементы. (Здесь, конечно, все свопы также не являются операциями, между двумя равными индексами, но не в общем случае).

источник

2016-03-26 00:28:27

Спасибо. Отличное объяснение! – tfreiner

@tfreiner, вы очень желанны. :) –

Прогрессия алгоритма быстрой сортировки с равными элементами

ответ

Смежные вопросы