Реализация быстрой сортировки в Python [конкретные сбои ввода]
Я пишу код алгоритма quick_sort. Это код, который, насколько мне известно, должен работать и работает для большинства массивов, но не работает с [5, 3, 9, 8, 6] и выдает IndexError: индекс списка вне допустимого диапазона.
def quick_sort_array(A):
return quick_sort(A, 0, len(A)-1)
def quick_sort(A, l, r):
if l < r:
pivot = A[l]
left = l + 1
right = r
while left <= right:
while A[left] <= pivot:
left += 1
while A[right] >= pivot and left <= right:
right -= 1
if left <= right:
tmp = A[left]
A[left] = A[right]
A[right] = tmp
A[l] = A[right]
A[right] = pivot
quick_sort(A, l, right-1)
quick_sort(A, right+1, r)
Не могли бы вы помочь мне понять это? Спасибо
![Реализация быстрой сортировки в Python [конкретные сбои ввода]](https://i.stack.imgur.com/8Gjxq.png)
Спасибо @Ulrich, это тоже помогает.
Ответы 1
Ваша реализация этапа разделения быстрой сортировки дает сбой, когда стержень является самым большим элементом между началом части списка, который вы разбиваете на разделы, и концом списка. Цикл while, который увеличивает left, может продолжаться до тех пор, пока не выйдет за конец списка.
Чтобы решить эту проблему, вам нужно остановить первый внутренний цикл от прохождения right, точно так же, как вы уже предотвращаете right слишком далекое прохождение left. Я не проверял точно, какое граничное условие вы хотите, но простое копирование из второго внутреннего цикла, вероятно, сработает:
while A[left] <= pivot and left <= right:
left += 1
while A[right] >= pivot and left <= right:
right -= 1
В вызове, который завершается ошибкой, каковы значения параметров? Это должно позволить вам быстро найти ошибку. Кроме того, попробуйте найти видеоруководство, показывающее, как выполнять код с помощью отладчика.