¿Qué está mal con mi algoritmo de ordenamiento rápido recursivo en Python?

Mi algoritmo tiene dos funciones. La primera es “partition” que toma el primer elemento de la lista como pivote y coloca todos los elementos mayores que él después de él y todos los más pequeños antes que él, y yo lo he probado y funciona muy bien. La segunda función es “quicksort” y utiliza “partition” recursivamente para ordenar toda la lista. Cuando ejecuto el código en PyCharm, dice que el límite máximo de recursión se ha excedido y algunos otros errores. Aquí está el código:

Arr = [81, 4, 73, 1, 98, 69, 300, 14, 7, 420, 190, 8, 9] def partition(low, high): lo = bajo hi = alto pivote = arr[lo] while lo < hi: while arr[lo] <= pivote: lo += 1 while arr[hi] > pivote: hi -= 1 if hi > lo: arr[lo], arr[hi] = arr[hi], arr[lo] arr[0], arr[hi] = arr[hi], arr[0] return hi def quicksort(l, h): if l < h: j = partition(l, h) quicksort(l, j) quicksort(j + 1, h) quicksort(0, 12) print(arr)

PD: Soy principiante (sólo llevo 2 meses de Python) así que por favor trate de explicar de manera sencilla.
¡Gracias de antemano!

davy.ai

May 28, 2023 at 7:35 pm

El código provoca un error debido a que se excede la profundidad máxima de recursión, lo que ocurre cuando una función se llama a sí misma una y otra vez hasta que alcanza el número máximo de llamadas, causando que el programa se bloquee.

En este caso, la función quicksort() se llama a sí misma recursivamente, pero no tiene un caso base para detener la recursión. El caso base debería verificar si la lista pasada tiene menos de o igual a un elemento, en cuyo caso debería devolver la lista tal cual.

Para solucionar el error, puede agregar un caso base a la función quicksort() verificando si h - l <= 1. Además, puede intercambiar las posiciones de j y j+1 en las llamadas recursivas a quicksort() ya que la función partition() coloca el pivote en la posición correcta y j no debería ser incluido en la segunda llamada recursiva.

Aquí está el código corregido:

arr = [81, 4, 73, 1, 98, 69, 300, 14, 7, 420, 190, 8, 9]

def partition(low, high):
    lo = low
    hi = high
    pivot = arr[lo]
    while lo < hi:
        while arr[lo] <= pivot:
            lo += 1
        while arr[hi] > pivot:
            hi -= 1
        if hi > lo:
            arr[lo], arr[hi] = arr[hi], arr[lo]
    arr[low], arr[hi] = arr[hi], arr[low]
    return hi

def quicksort(l, h):
    if h - l <= 1:
        return
    j = partition(l, h)
    quicksort(l, j)
    quicksort(j + 1, h)

quicksort(0, len(arr)-1)
print(arr)

Esto debería ordenar la lista sin levantar ningún error.

Answer

davy.ai

May 28, 2023 at 7:35 pm
El código provoca un error debido a que se excede la profundidad máxima de recursión, lo que ocurre cuando una función se llama a sí misma una y otra vez hasta que alcanza el número máximo de llamadas, causando que el programa se bloquee.

En este caso, la función quicksort() se llama a sí misma recursivamente, pero no tiene un caso base para detener la recursión. El caso base debería verificar si la lista pasada tiene menos de o igual a un elemento, en cuyo caso debería devolver la lista tal cual.

Para solucionar el error, puede agregar un caso base a la función quicksort() verificando si h - l <= 1. Además, puede intercambiar las posiciones de j y j+1 en las llamadas recursivas a quicksort() ya que la función partition() coloca el pivote en la posición correcta y j no debería ser incluido en la segunda llamada recursiva.

Aquí está el código corregido:
```
arr = [81, 4, 73, 1, 98, 69, 300, 14, 7, 420, 190, 8, 9]

def partition(low, high):
    lo = low
    hi = high
    pivot = arr[lo]
    while lo < hi:
        while arr[lo] <= pivot:
            lo += 1
        while arr[hi] > pivot:
            hi -= 1
        if hi > lo:
            arr[lo], arr[hi] = arr[hi], arr[lo]
    arr[low], arr[hi] = arr[hi], arr[low]
    return hi

def quicksort(l, h):
    if h - l <= 1:
        return
    j = partition(l, h)
    quicksort(l, j)
    quicksort(j + 1, h)

quicksort(0, len(arr)-1)
print(arr)
```
Esto debería ordenar la lista sin levantar ningún error.

Comments are closed.

es.davy.ai

¿Tienes una pregunta?

¿Qué está mal con mi algoritmo de ordenamiento rápido recursivo en Python?

Answer

davy.ai