QuickSort in Python - il programma si blocca per input di dimensioni maggiori?

Question

Abbastanza confuso su questo perché ho verificato l'output logico corretto per testicoli di dimensioni sufficientemente ridotte (N = 20). Provo a fare N = 10.000 numeri e il programma si blocca e non capisco perché ... Ho implementato l'algoritmo nel modo più semplice possibile.

Inoltre, chiamare sorted(data) sulla mia lista N = 10k sembra funzionare quasi istantaneamente. Quindi sono convinto che il mio algoritmo resti bloccato da qualche parte.

Ecco il codice:

def QuickSort(array): 
    qsort(array, 0, len(array)) 


def qsort(arr, left, right): 
    if ((right - left) < 2): 
     return 

    pivotIndex = choosePivot0(arr, left, right) 

    newPivotIndex = partition(arr, pivotIndex, left, right) 

    qsort(arr, 0, newPivotIndex) 
    qsort(arr, newPivotIndex + 1, right) 

def partition(arr, pivotIndex, left, right): 
    swap(arr, pivotIndex, left) 
    pivot = arr[left] 
    i = left + 1 
    for j in range(left+1, right): 
     if (arr[j] < pivot): 
      swap(arr, i, j) 
      i = i + 1 

    swap(arr, left, i-1) #put pivot back where it belongs 
    #cobj.count = cobj.count + (right - left - 1) #add m-1 the #of comparisons 
    return (i-1) #give back where the pivot resides 



def swap(array, i, j): 
    temp = array[i] 
    array[i] = array[j] 
    array[j] = temp 

def choosePivot0(array, left, right): 
    return randint(left, right-1) #random 

quindi sono abbastanza perso sul motivo per cui questo potrebbe accadere. Grazie per qualsiasi aiuto.

Answer 1

Sembra che ci sia un errore di battitura nella seguente riga:

qsort(arr, 0, newPivotIndex) 

penso che dovrebbe essere simile a questo.

qsort(arr, left, newPivotIndex) 

In caso contrario, la funzione funzionerà in qualche modo solo per alcuni set di dati di input. Questo è il motivo per cui l'algoritmo si blocca.

Answer 2

Nota: non ho controllato il tuo algoritmo quindi potrebbe esserci un problema con esso/python potrebbe non piacere per qualche motivo ma: L'ordinamento rapido migliorerà approssimativamente il tempo di ordinamento da N^2 a N log (N) , ma forse brutto come N^2 a seconda dei dati di input. Con i dati ottimali, N = 10.000 rispetto a N = 20, sarebbe un fattore di 40.000/26 = 1538 volte più lento. Forse è solo l'elaborazione?

Con i dati del caso peggiore sarà 100.000.000/400 = 25.000 volte più lento. Quali sono i tuoi dati?

Answer 3

Python si blocca spesso per funzioni ricorsive profonde, a volte termina semplicemente la sessione corrente (se si sta provando in IDLE) e avvia una nuova sessione senza dare alcun output. Prova questo: import sys; sys.setrecursionlimit(2**30), questo può aiutare, anche se non sempre.