QuickSort en Python: ¿el programa se bloquea para tamaños de entrada más grandes?

Question

Bastante confundido acerca de esto porque he verificado la salida lógica correcta para testcases lo suficientemente pequeños (N = 20). Intento hacer N = 10,000 números y el programa simplemente se cuelga y no entiendo por qué ... Implementé el algoritmo de la manera más simple posible.

Además, llamar al sorted(data) en mi N = lista de 10k parece funcionar casi al instante. Así que estoy convencido de que mi algoritmo simplemente se queda atascado en alguna parte.

Aquí está el código:

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 

así que estoy bastante perdido en cuanto a por qué esto podría estar sucediendo. Gracias por cualquier ayuda.

Answer 1

Parece que hay un error tipográfico en la siguiente línea:

qsort(arr, 0, newPivotIndex) 

creo que debe ser así.

qsort(arr, left, newPivotIndex) 

De lo contrario, la función funcionará de alguna manera solo para algunos de los conjuntos de datos de entrada. Es por eso que el algoritmo se atasca.

Answer 2

Nota: No he comprobado su algoritmo, por lo que tal vez haya un problema con él/Python puede no gustarle por alguna razón, pero: La clasificación rápida mejorará aproximadamente el tiempo de clasificación de N^2 a N log (N) , pero tal vez tan malo como N^2 dependiendo de los datos de entrada. Con datos óptimos, N = 10,000 en comparación con N = 20, sería un factor de 40,000/26 = 1538 veces más lento. Tal vez es solo el procesamiento?

Con los peores datos de casos, será 100,000,000/400 = 25,000 veces más lento. ¿Cuál es tu información?

Answer 3

Python a menudo se cuelga para funciones recursivas profundas, a veces simplemente finaliza la sesión actual (si lo está intentando en IDLE), y comienza una nueva sesión sin dar ninguna salida en absoluto. Pruebe esto: import sys; sys.setrecursionlimit(2**30), esto puede ayudar, aunque no siempre.