Ordenamiento Rápido

9.1 Definición de Ordenamiento Rápido

Ordenamiento Rápido (Quick Sort) es un algoritmo eficiente de ordenamiento que utiliza el enfoque de "divide y vencerás". Funciona eligiendo un elemento pivote, dividiendo el array en dos subarrays: elementos menores que el pivote y elementos mayores que el pivote, y luego aplicando recursivamente el mismo proceso a cada subarray.

El algoritmo de Quick Sort surgió como un intento de resolver el problema de “cómo mover rápidamente los elementos pequeños a la izquierda y los grandes a la derecha”. Supongamos que tenemos el elemento más pequeño al extremo derecho, ¿será posible moverlo rápidamente, si no a su posición final, al menos cerca de ella? Esto reduciría significativamente la cantidad de comparaciones innecesarias.

Principio de funcionamiento:

1. Selección del elemento pivote:

Elegimos un elemento del array como pivote. Esto puede ser el primer elemento, el último, el del medio o uno aleatorio. A veces es el promedio de tres elementos aleatorios.

2. División (partitioning):

Movemos todos los elementos menores que el pivote a la parte izquierda del array, y todos los elementos mayores que el pivote a la parte derecha. Como resultado, el pivote termina en su posición final en el array ordenado.

3. Aplicación recursiva:

Aplicamos recursivamente el proceso a los subarrays izquierdo y derecho, excluyendo el pivote.

Proceso paso a paso

1. Elegimos el elemento pivote.
2. Movemos los elementos menores que el pivote a la izquierda, y los elementos mayores a la derecha.
3. Aplicamos recursivamente el proceso a los subarrays.

Complejidad temporal y espacial de Quick Sort

Complejidad temporal:

• En el peor de los casos: O(n^2) — ocurre cuando cada vez se elige el peor elemento pivote (por ejemplo, cuando el array ya está ordenado).
• En el caso promedio: O(n log n) — para datos distribuidos aleatoriamente.
• En el mejor de los casos: O(n log n) — cuando el array se divide cada vez en partes iguales.

Complejidad espacial:

O(log n) — se requiere para almacenar la pila de llamadas recursivas, si se utiliza recursión de cola y los elementos pivotes se eligen adecuadamente.

9.2 Implementación del algoritmo de Quick Sort

Implementación en Python:

def quick_sort(arr):
    if len(arr) <= 1:
        return arr  # Caso base: array con 0 o 1 elemento ya está ordenado
    
    pivot = arr[len(arr) // 2]  # Elegimos el elemento pivote
    left = [x for x in arr if x < pivot]  # Elementos menores que el pivote
    middle = [x for x in arr if x == pivot]  # Elementos iguales al pivote
    right = [x for x in arr if x > pivot]  # Elementos mayores que el pivote
    
    return quick_sort(left) + middle + quick_sort(right)

# Ejemplo de uso:
arr = [3, 6, 8, 10, 1, 2, 1]
sorted_arr = quick_sort(arr)
print("Array ordenado:", sorted_arr)
# Output: Array ordenado: [1, 1, 2, 3, 6, 8, 10]

Ejemplo de funcionamiento del algoritmo

Tomemos un ejemplo de array: [3, 6, 8, 10, 1, 2, 1]

Primer paso:

• Elemento pivote: 8
• Elementos izquierdos: [3, 6, 1, 2, 1]
• Elementos medios: [8]
• Elementos derechos: [10]

Ordenamiento recursivo de la parte izquierda [3, 6, 1, 2, 1]:

• Elemento pivote: 1
• Elementos izquierdos: []
• Elementos medios: [1, 1]
• Elementos derechos: [3, 6, 2]

Ordenamiento recursivo de la parte derecha [3, 6, 2]:

• Elemento pivote: 6
• Elementos izquierdos: [3, 2]
• Elementos medios: [6]
• Elementos derechos: []

Ordenamiento recursivo de la parte izquierda [3, 2]:

• Elemento pivote: 2
• Elementos izquierdos: []
• Elementos medios: [2]
• Elementos derechos: [3]

Resultado de la fusión: [1, 1, 2, 3, 6] para la parte izquierda, [10] para la parte derecha, y [8] para la media.

Array ordenado final: [1, 1, 2, 3, 6, 8, 10]