Python Почему эта сортировка не сортируется правильно?

Question

Я пытаюсь реализовать функцию quicksort с помощью python в течение последних трех недель, но я всегда добираюсь до этой точки, и она сортируется в основном, но есть несколько вещей на своем месте.

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

Я выбрал стержень, чтобы быть первым объектом в списке, «низким», а затем сравним его с остальной частью списка. Если объект в списке индексов «low» больше, чем индекс списка «i» (в моем цикле for), то я переключаю «i» на «E» (сначала индексируется на элемент «low + 1»), если он переключатель, «E» увеличивается. Даже если он не переключается, «i» увеличивается (из-за цикла for).

После того, как мой цикл завершен, я декремент «E» (с индексом его наибольшим номером в списке ниже, чем мой стержень), а затем переключить его с «низким» (индекс поворота)

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

Я считаю, что это так, как работает quicksort, но я не смог заставить его работать. Если вы знаете, что мне не хватает, или если это только одна из моих строк, сообщите мне. Любая помощь с этой проблемой была бы весьма признательна.

(PS. «Основная» функция просто проездом список длины 20 с переменными 0-19 значения в мою быструю сортировку и Python встроенной сортировки)

import random 


def quick(A, low, high): 
    if high <= low: 
     return 
    elif high > low: 
     E = low+1 
     for i in range(E, high): 
      if A[low] > A[i]: 
       A[i], A[E] = A[E], A[i] 
       E +=1 
     E -= 1 
     A[low], A[E] = A[E], A[low] 
     quick(A, low, E-1) 
     quick(A, E+1, high) 


def main(): 
    listA = [] 
    listB = [] 
    for i in range(20): 
     int = random.randrange(0, 19) 
     listA.append(int) 
    for i in range(len(listA)): 
     listB.append(listA[i]) 
    print("List A (before sort)" + str(listA)) 
    print("List B (before sort)" + str(listB)) 
    quick(listA, 0, len(listA)-1) 
    print("\nList A (after sort)" + str(listA)) 
    print("List B (before sort)" + str(listB)) 
    listB.sort() 
    print("\nList A (after sort)" + str(listA)) 
    print("List B (after sort)" + str(listB)) 


main() 

Answer 1

Ваша проблема в том, что вы «игнорируя одно число с каждым расколом. range(min, max) дает список, который включает в себя, но не minmax, окончание, а на max-1

quick(listA, 0, len(listA)-1)

должен быть

quick(listA, 0, len(listA)),

и

quick(A, low, E-1)

должен be

quick(A, low, E).