QuickSort - RuntimeError: превышена максимальная глубина рекурсии

Question

Я просил простую быструю сортировку, но у меня проблемы с ней.

def partition(A, p, r): 
    x = A[r] 
    i = p 
    j = r 
    while True: 
     while A[i] < x: 
      i+=1 
     while x < A[j]: 
      j-=1 
     if i < j: 
      A[i], A[j] = A[j], A[i] 
      i += 1 
      j -= 1 
     else: 
      return j 

def quickSort(A, p, r): 
    if p<r: 
     q = partition(A, p, r) 
     quickSort(A, p, q-1) 
     quickSort(A, q+1, r) 

def quickSortMainReq(A): 
    quickSort(A, 0, len(A)-1) 
    return A 

Все в порядке, пока у вас нет большого массива. Например, print quickSortMainReq(range(994)) работает. print quickSortMainReq(range(995)) нет. Когда я устанавливаю свой x в [(p + r) // 2], он работает, но я должен использовать правую ось . Я понятия не имею, почему. Он должен работать для всех.

Answer 1

не затруднит себя;) Посмотрите на мой маленький, удивительный пример Quick Sort