Quicksort максимальная глубина рекурсии превысила

Question

Я реализовал алгоритм быстрой сортировки на практике Python, вот мой код:

def sort(array): 
    if len(array) > 1: 
     pivot = array[0] 
     left = [] 
     right = [] 
     equal = [] 
     for x in array: 
      if x < pivot: 
       left.append(x) 
      elif x == pivot: 
       equal.append(x) 
      else: 
       right.append(x) 
     return sort(left)+equal+sort(right) 
    return array 

Теперь, алгоритм работает нормально, но если я удалить equal список и сделать свой цикл, как это:

for x in array: 
     if x < pivot: 
      left.append(x) 
     else: 
      right.append(x) 
    return sort(left) + sort(right) 

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

Answer 1

Возможно, вам не нужен список equal, но его наличие имеет решающее значение. Поместив элементы, которые попадают туда в список right, вы вынуждаете алгоритм поддерживать sort() элементы, которые уже отсортированы. Вот почему ваш предел рекурсии превышен.

Добавляя print "sorting", array в начале вашей функции, вы можете увидеть, что происходит:

>>> sort([3,1,2]) 
('sorting ', [3, 1, 2]) 
('sorting ', [1, 2]) 
('sorting ', []) 
('sorting ', [1, 2]) 
('sorting ', []) 
('sorting ', [1, 2]) 
('sorting ', []) 
... etc. until crash 

Answer 2

Ось всегда переходит в right в качестве нулевого элемента, и получает выбран еще раз, когда вы рекурсию на right. Так как right также содержит все, что равно или больше этого, следующий звонок поместит все из текущих элементов в новый right.

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

Вам не нужно иметь equalсписок, но вы должны принять по крайней мере, выбранный стержень из рекурсии, так что следующий вызов вниз выбирает другой. Так что выбирайте его таким образом:

pivot = array.pop(0) 

и корректировать реконструкцию отсортированного списка:

return sort(left) + [pivot] + sort(right)