8.7. Ordenación Rápida (QuickSort) - Definición y Algoritmo

Definición

El Ordenamiento Rápido, conocido en inglés como QuickSort, es un algoritmo de ordenación eficiente y ampliamente utilizado. Fue desarrollado por Tony Hoare en 1959 y publicado en 1961. QuickSort emplea el enfoque de divide y vencerás para ordenar una lista de elementos. Es reconocido por su eficiencia y su buen rendimiento en la práctica, a pesar de tener un peor caso menos favorable en comparación con algunos otros algoritmos.

QuickSort trabaja seleccionando un pivote y particionando la lista en dos sublistas: una con elementos menores que el pivote y otra con elementos mayores. Luego, se aplica recursivamente el mismo proceso a las sublistas.

Algoritmo

  1. Elegir un pivote: Seleccionar un elemento de la lista como pivote.
  2. Partición: Reordenar la lista de manera que todos los elementos menores que el pivote queden a la izquierda y los mayores a la derecha.
  3. Recursión: Aplicar recursivamente el algoritmo a las dos sublistas generadas.

Pseudocódigo

procedure quickSort(A: list of sortable items, low: int, high: int)
    if low < high then
        pi = partition(A, low, high)
        quickSort(A, low, pi - 1)
        quickSort(A, pi + 1, high)
end procedure

procedure partition(A: list of sortable items, low: int, high: int)
    pivot = A[high]
    i = (low - 1)
    for j = low to high - 1 do
        if A[j] <= pivot then
            i = i + 1
            swap A[i] with A[j]
    swap A[i + 1] with A[high]
    return (i + 1)
end procedure

Descripción del Pseudocódigo

  1. QuickSort:

    • Si el índice low es menor que high, significa que hay más de un elemento en la sublista.
    • Se llama a la función partition para dividir la lista y obtener el índice del pivote (pi).
    • Se aplica recursivamente quickSort a las sublistas generadas por la partición.

  2. Partition:

    • Se selecciona el último elemento de la lista como pivote.
    • Se inicializa el índice i justo antes del primer elemento.
    • Se recorre la lista desde low hasta high - 1. Si el elemento actual es menor o igual al pivote, se incrementa i y se intercambia el elemento actual con el elemento en i.
    • Finalmente, se coloca el pivote en su posición correcta intercambiándolo con el elemento en i + 1 y se retorna el índice del pivote.