Как работает этот алгоритм сортировки?

Question

надеюсь, что у вас будет хороший день и хороший благодарение, если вы живете в Канаде или США.

Итак, у меня есть этот вопрос, который просит меня объяснить, почему этот алгоритм сортировки правильно сортирует массив. Однако я действительно не понимаю, как этот алгоритм действительно работает.

Рассмотрим следующий пример очень простой и элегантный алгоритм сортировки (?):

SomeSort(A,b,e) 
if e = b + 1 then 
    if A[b] > A[e] then 
     exchange A[b] and A[e] 
    end if 
else if e > b + 1 then 
    p ←− [(e-b+1)/3] 
    SomeSort(A,b,e − p) 
    SomeSort(A,b + p,e) 
    SomeSort(A,b,e − p) 
end if 

(а) Объясните, почему SomeSort правильно сортирует свой входной массив A, предполагая, что п = е - Ь + 1 длина (ваш аргумент не обязательно должен быть формальным доказательством, но должен быть достаточно подробным, чтобы быть уверенным в ).

(b) Найдите повторение для наихудшего времени работы SomeSort. Дайте плотную (т. Е. Θ) асимптотику , привязанную к худшему времени работы SomeSort (Подсказка: для простоты предположим, что n = 3 k для некоторой константы k).

(c) Сравнивая SomeSort с сортировкой вставки, сгруппируйте сортировку, сортировку кучи и quicksort, если этот простой алгоритм эффективен.

Так что я понял из этого алгоритма является то, что:

Первое, если оператор проверяет, если указатели б и е в соседних позициях с е впереди б, и если они проверить, если значение в точке Ь больше , Если это тогда, замените их значениями.

Если else, похоже, проверяет, что e впереди и не смежна с b, прежде чем назначать длину массива, которая является разницей между b и e, прежде чем делить ее на 3 на p.

Затем он переписывается с новыми указателями, причем b остается неизменным, а e теперь является старым e минус третья разница между старыми e и b.

Он также рекурсирует, когда b является старым b плюс третью разницей между старыми e и b.

Затем он повторяет последний раз с теми же указателями, что и первая рекурсия.

Так что я действительно не понимаю, почему он повторяет те же значения дважды, когда e становится e-p. Я также не совсем уверен, как рекурсия третьей разностью будет правильно сортировать массив, не пропуская ничего.

Если вы могли бы помочь мне понять эти рекурсии или что-то, что мне здесь не хватает, это было бы здорово. Я даже не могу начать отвечать на вторую часть этого вопроса о нахождении худшего случая, не понимая алгоритма, так что это меня очень раздражает. Благодаря!

Answer 1

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

Прогулка по алгоритму с

• 3-элемент массива а, уже в порядке
• 9-элемент массива а, в обратном порядке
• 7-элемент массива а, омлет, такие как [ 1, 4, 2, 8, 5, 7, 0]

В конце этого вы должны понимать, как работает алгоритм, почему он работает, и которые являются лучшими и худшими случаями.