QuickSort - RuntimeError: maximale Rekursionstiefe überschritten

Question

Ich schrieb einen einfachen Quicksort, aber ich habe Probleme damit.

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 

Alles ist gut, bis Sie keine große Array haben. Zum Beispiel funktioniert print quickSortMainReq(range(994)) funktioniert. print quickSortMainReq(range(995)) ist nicht. Wenn ich mein x auf [(p + r) // 2] setze, funktioniert es, aber ich muss den rechten Drehpunkt verwenden Ich habe keine Ahnung warum. Es sollte für alle funktionieren.

Answer 1

nicht komplizierter selbst;) Quick Sort