В образовательных целях я пытаюсь изучить алгоритм быстрой сортировки. Вместо того, чтобы проверять реализацию в Интернете или пытаться реализовать непосредственно из псевдокода в Википедии, Я пробую "жесткий путь".
Я смотрел эту лекцию из CS50 https://www.youtube.com/watch?v=aQiWF4E8flQ&t=305s, чтобы понять, как перемещаются числа при «быстрой сортировке». Моя реализация, которую я покажу ниже, отлично работает для примера, представленного на видео. Пример на видео исходного несортированного массива таков:
Это мой код в Python 3:
len_seq = int(input())
print("len_seq",len_seq)
seq_in = list(map(int,(input()).split()))
print("seq_in",seq_in)
def my_quick_sort(seq):
wall_index = 0
pivot_corect_final_index_list = []
while wall_index<len_seq:
pivot = seq[-1]
print("pivot",pivot)
print("wall_index",wall_index)
for i in range(wall_index,len_seq):
print ("seq[i]",seq[i])
if seq[i]<pivot:
print("before inside swap,", seq)
seq[wall_index],seq[i]=seq[i],seq[wall_index]
print("after inside swap,", seq)
wall_index = wall_index + 1
print ("wall_index",wall_index)
print("before outside swap,", seq)
seq[wall_index],seq[-1]=seq[-1],seq[wall_index]
print("after outside swap,", seq)
pivot_corect_final_index = wall_index
print ("pivot correct final index",pivot_corect_final_index)
pivot_corect_final_index_list.append(pivot_corect_final_index)
print ("pivot_corect_final_index_list",pivot_corect_final_index_list)
wall_index = wall_index + 1
print ("wall_index",wall_index)
return seq
print(my_quick_sort(seq_in))
Чтобы использовать пример Гарварда CS50 в моем коде, вам нужно ввести это:
9
6 5 1 3 8 4 7 9 2
Алгоритм работает нормально и возвращает правильный результат:
[1, 2, 3, 4, 5, 6, 7, 8, 9]
Продолжая свое исследование, я попытался реализовать пример Академии Хана: https://www.khanacademy.org/computing/computer-science/algorithms/quick-sort/a/overview-of-quicksort
Несортированный список в этом случае:
[9, 7, 5, 11, 12, 2, 14, 3, 10, 6]
Вам нужно ввести следующее в мой код, чтобы запустить его:
10
9 7 5 11 12 2 14 3 10 6
В отличие от гарвардского примера, в данном случае моя реализация работает неидеально. Он возвращает:
[5, 2, 3, 6, 7, 9, 10, 11, 12, 14]
Как видите, все числа, которые я рассматривал как опорные, заканчиваются в правильной позиции. Однако некоторые числа за разворотами неверны.
Читая статью академии хана, кажется, что моя реализация правильная на этапе разделения. Однако она неверна на этапе завоевания. Я стараюсь не искать окончательного решения. Я пытаюсь улучшить то, что я построил до сих пор. Не уверен, что это лучший метод, но сейчас я его пробую.
Как я могу исправить шаг завоевания? Нужно ли внедрять рекурсивный подход? Как я могу сделать это внутри моего итеративного процесса? И следует ли вводить этот шаг после успешного лечения каждого поворота?
Спасибо за терпение при чтении этого длинного поста.
