es.davy.ai

Preguntas y respuestas de programación confiables

¿Tienes una pregunta?

Si tienes alguna pregunta, puedes hacerla a continuación o ingresar lo que estás buscando.

Contando intercambios y comparaciones en Quicksort (Python)

06 Aug, 2023 Programación

Estoy intentando contar las operaciones de intercambio y comparación en un quicksort. Creo que he configurado los contadores en las ubicaciones correctas, pero debido a la recursión, nunca obtengo la cantidad correcta para estos valores. Para ‘almacenar’ los valores a lo largo de la recursión, los paso como parámetros (qui_swap y qui_comp).

Por ejemplo: cuando dejo que este algoritmo ordene una lista de 500 enteros, devuelve 120 intercambios y 1 comparación.

A continuación está mi código:

qui = quicksort(numbers, 0, len(numbers)-1, 0, 0)

def partition(numbers, start_index, end_index, qui_swap):

# Selecciona el valor medio como pivote.
    midpoint = start_index + (end_index - start_index) // 2
    pivot = numbers[midpoint]

    # 'low' y 'high' comienzan en los extremos del segmento de la lista
    # y se mueven uno hacia el otro.
    low = start_index
    high = end_index

    done = False
    while not done:
        # Incrementa 'low' mientras que numbers[low] < pivot
        while numbers[low] < pivot:
            low = low + 1

        # Decrementa 'high' mientras que pivot < numbers[high]
        while pivot < numbers[high]:
            high = high - 1

        # Si 'low' y 'high' se han cruzado, se termina el bucle.
        # Si no, se intercambian los elementos, se incrementa 'low' y se decrementa 'high'.
        if low >= high:
            done = True
        else:
            temp = numbers[low]
            numbers[low] = numbers[high]
            numbers[high] = temp
            low += 1
            high -= 1
            qui_swap += 1

    # 'high' es el último índice en el segmento izquierdo.
    return (high, qui_swap)

def quicksort(numbers, start_index, end_index, qui_swap, qui_comp):
    # Solo intenta ordenar el segmento de la lista si hay al menos 2 elementos.

    if end_index <= start_index:
        return

    # Particiona el segmento de la lista.
    # cuenta las comparaciones aquí
    qui_comp += 1
    high = partition(numbers, start_index, end_index, qui_swap)
    qui_swap = high[1]

    # Ordena recursivamente el segmento izquierdo.
    quicksort(numbers, start_index, int(high[0]), qui_swap, qui_comp+1)

    # Ordena recursivamente el segmento derecho.
    quicksort(numbers, int(high[0]) + 1, end_index, qui_swap, qui_comp+1)

    return (qui_swap, qui_comp)
Tags:  , ,

Answer

  1. Avatar for davy.ai
    davy.ai

    Parece que estás tratando de hacer un seguimiento del número de intercambios y comparaciones realizadas en el algoritmo de ordenación rápida (quicksort). Sin embargo, debido a la recursividad, los valores que obtienes no son precisos.

    Para resolver esto, puedes intentar implementar una función auxiliar que lleve un registro del número de intercambios y comparaciones realizadas en cada iteración del algoritmo. Esta función puede devolver los valores actualizados de intercambio y comparación, que luego se pueden usar en las iteraciones subsiguientes.

    Aquí hay un ejemplo de implementación de dicha función:

    def quicksort_helper(numbers, start_index, end_index, qui_swap, qui_comp):
    if end_index <= start_index:
        return qui_swap, qui_comp

    high, swap, comp = partition(numbers, start_index, end_index, qui_swap, qui_comp)
    swap += qui_swap
    comp += qui_comp

    swap, comp = quicksort_helper(numbers, start_index, high, swap, comp)
    swap, comp = quicksort_helper(numbers, high + 1, end_index, swap, comp)

    return swap, comp

def partition(numbers, start_index, end_index, qui_swap, qui_comp):
    midpoint = start_index + (end_index - start_index) // 2
    pivot = numbers[midpoint]

    low = start_index
    high = end_index

    done = False
    while not done:
        while numbers[low] < pivot:
            low += 1
            qui_comp += 1

        while pivot < numbers[high]:
            high -= 1
            qui_comp += 1

        if low >= high:
            done = True
        else:
            temp = numbers[low]
            numbers[low] = numbers[high]
            numbers[high] = temp
            low += 1
            high -= 1
            qui_swap += 1

    return high, qui_swap, qui_comp

def quicksort(numbers):
    qui_swap, qui_comp = 0, 0
    return quicksort_helper(numbers, 0, len(numbers)-1, qui_swap, qui_comp)

    En esta implementación, la función quicksort_helper es una función auxiliar recursiva que lleva un registro del número de intercambios y comparaciones realizadas hasta el momento en el algoritmo. Devuelve los valores actualizados de intercambio y comparación para la siguiente iteración.

    La función partition también se actualiza para incluir el número de intercambios y comparaciones realizadas en la iteración actual.

    Finalmente, la función quicksort llama a la función quicksort_helper con valores iniciales de qui_swap y qui_comp establecidos en 0.

    Con esta implementación, deberías poder contar con precisión el número de intercambios y comparaciones realizadas en el algoritmo de ordenación rápida, incluso con recursividad.

Comments are closed.