0
Я пытаюсь реализовать быструю сортировку в питоне:Почему границы моей реализации quicksort не оправдались?
def partition(ls):
if len(ls) == 0:
return 0
pivot = ls[0]
i = 0
j = 1
while j < len(ls):
if ls[j] <= pivot:
i += 1
temp = ls[i]
ls[i] = ls[j]
ls[j] = temp
j += 1
ls[0] = ls[i]
ls[i] = pivot
return i
assert(partition([1,2]) == 0)
assert(partition([3,2]) == 1)
assert(partition([3,2,1,4,5]) == 2)
assert(partition([]) == 0)
assert(partition([45]) == 0)
def sort(ls):
if len(ls) == 0:
return
pivotIndex = partition(ls)
sort(ls[0:pivotIndex])
sort(ls[(pivotIndex + 1):len(ls)])
ls = [54,1,3,2,4,3,5,4]
sort(ls)
print ls
На основании моих заявлений утверждают, я знаю, что мой алгоритм раздел работает отлично.
Однако моя функция сортировки возвращает ошибочные результаты. Этот фрагмент кода печатает
[4, 1, 3, 2, 4, 3, 5, 54]
Каковы должны быть границы рекурсивных вызовов сортировки? Я пытаюсь разбить подсписку слева от точки поворота и подслова справа от стержня, оба из которых не содержат самого стержня.
Просить незнакомых людей обнаружить ошибки в вашем коде неэффективно. Есть бесчисленные реализации quicksort там. Я бы предложил перейти через ваш код и сравнить его поведение с реализацией хорошо известной реализации. –
Кроме того, вы можете просто поместить некоторые 'print' в свой код, чтобы узнать, что делают ваши индексы, что позволит вам понять, что они делают неправильно. – BrenBarn
Ваши утверждения только показывают, что 'partition' помещает элемент поворота в правый индекс, а не тот раздел, который правильно. Кроме того, вы копируете списки при разрезании (конструкция 'ls [start: end]'), такой вид пропускает точку реализации быстрой сортировки на месте. Вы должны сделать начальный и конечный индексы диапазона, над которым следует работать как параметры для 'sort()'. – millimoose