4 - QuickSort

QuickSort es uno de los ordenamientos más usados en la práctica por su eficiencia promedio O(n log n) y su bajo uso de memoria. Funciona al elegir un pivote, particionar la lista en torno a él y ordenar recursivamente las particiones.

4.1 Idea general: pivote y particiones

El pivote define un punto de corte: todos los elementos menores (o iguales) quedan a su izquierda y los mayores a su derecha. Luego QuickSort se aplica recursivamente a cada lado hasta que los subarrays sean de tamaño 0 o 1.

4.2 Estrategias para elegir pivote

• Primer elemento: simple pero vulnerable a datos ya ordenados.
• Último elemento: igual de simple, también expuesto a peores casos.
• Aleatorio: reduce la probabilidad de peores casos sistemáticos.
• Mediana de tres: calcula la mediana entre primero, medio y último; suele mejorar la calidad del pivote con bajo costo.

4.3 Particionamiento: esquemas clásicos

Los dos esquemas más usados son Lomuto y Hoare. Lomuto es más simple; Hoare reduce intercambios.

# Particionamiento de Lomuto
def particion_lomuto(arr, inicio, fin):
  pivote = arr[fin]
  i = inicio - 1
  for j in range(inicio, fin):
    if arr[j] <= pivote:
      i += 1
      arr[i], arr[j] = arr[j], arr[i]
  arr[i + 1], arr[fin] = arr[fin], arr[i + 1]
  return i + 1

# Particionamiento de Hoare
def particion_hoare(arr, inicio, fin):
  pivote = arr[(inicio + fin) // 2]
  i = inicio - 1
  j = fin + 1
  while True:
    i += 1
    while arr[i] < pivote:
      i += 1
    j -= 1
    while arr[j] > pivote:
      j -= 1
    if i >= j:
      return j  # indice que separa las particiones
    arr[i], arr[j] = arr[j], arr[i]

4.4 Recursión en subarrays izquierdo y derecho

Tras particionar, se invoca QuickSort sobre cada lado. El esquema de llamada cambia según la función de partición:

def quicksort_lomuto(arr, inicio, fin):
  if inicio >= fin:
    return
  p = particion_lomuto(arr, inicio, fin)
  quicksort_lomuto(arr, inicio, p - 1)
  quicksort_lomuto(arr, p + 1, fin)

def quicksort_hoare(arr, inicio, fin):
  if inicio >= fin:
    return
  p = particion_hoare(arr, inicio, fin)
  quicksort_hoare(arr, inicio, p)
  quicksort_hoare(arr, p + 1, fin)

4.5 Implementación en Python

Versión completa usando mediana de tres y partición de Lomuto:

def mediana_de_tres(arr, inicio, fin):
  medio = (inicio + fin) // 2
  if arr[medio] < arr[inicio]:
    arr[medio], arr[inicio] = arr[inicio], arr[medio]
  if arr[fin] < arr[inicio]:
    arr[fin], arr[inicio] = arr[inicio], arr[fin]
  if arr[fin] < arr[medio]:
    arr[fin], arr[medio] = arr[medio], arr[fin]
  return medio

def particion_lomuto_mediana(arr, inicio, fin):
  m = mediana_de_tres(arr, inicio, fin)
  arr[m], arr[fin] = arr[fin], arr[m]  # mover pivote al final
  pivote = arr[fin]
  i = inicio - 1
  for j in range(inicio, fin):
    if arr[j] <= pivote:
      i += 1
      arr[i], arr[j] = arr[j], arr[i]
  arr[i + 1], arr[fin] = arr[fin], arr[i + 1]
  return i + 1

def quicksort(arr, inicio, fin):
  if inicio >= fin:
    return
  p = particion_lomuto_mediana(arr, inicio, fin)
  quicksort(arr, inicio, p - 1)
  quicksort(arr, p + 1, fin)

4.6 Complejidad temporal

• Caso promedio: O(n log n) gracias a particiones balanceadas en expectativa.
• Peor caso: O(n^2) cuando el pivote genera particiones muy desbalanceadas (datos ya ordenados con pivote fijo).

4.7 Cómo evitar el peor caso

• Elegir pivote aleatorio o mediana de tres reduce la probabilidad de caer en particiones extremas.
• Alternar a Insertion Sort en subarrays pequeños (<= 16) mejora las constantes y evita recursiones profundas.
• Limitar la profundidad de recursión y caer a HeapSort si se supera un umbral (estrategia introsort).

4.8 Ventajas y desventajas

• Ventajas: muy rápido en promedio; trabaja in-place con O(1) memoria extra; fácil de adaptar a distintos tipos de datos.
• Desventajas: peor caso cuadrático si el pivote es deficiente; no es estable; puede consumir mucha pila en entradas adversas.

4.9 Casos de uso ideales

• Arrays grandes: in-place y con buenas constantes en memoria caché.
• Datos sin requerimiento de estabilidad: rankings, ordenamientos de IDs, estructuras temporales.
• Algoritmos híbridos: base para introsort o conmutación a Insertion Sort en tramos cortos.

QuickSort sigue siendo la opción por defecto en muchas librerías gracias a su rendimiento promedio y bajo consumo de memoria.

4.10 Archivo único de trabajo

Siguiendo el formato del tutorial, reunimos todo en ordenamientos.py para ejecutar rápido.

# archivo: ordenamientos.py
def mediana_de_tres(arr, inicio, fin):
  medio = (inicio + fin) // 2
  if arr[medio] < arr[inicio]:
    arr[medio], arr[inicio] = arr[inicio], arr[medio]
  if arr[fin] < arr[inicio]:
    arr[fin], arr[inicio] = arr[inicio], arr[fin]
  if arr[fin] < arr[medio]:
    arr[fin], arr[medio] = arr[medio], arr[fin]
  return medio

def particion_lomuto_mediana(arr, inicio, fin):
  m = mediana_de_tres(arr, inicio, fin)
  arr[m], arr[fin] = arr[fin], arr[m]
  pivote = arr[fin]
  i = inicio - 1
  for j in range(inicio, fin):
    if arr[j] <= pivote:
      i += 1
      arr[i], arr[j] = arr[j], arr[i]
  arr[i + 1], arr[fin] = arr[fin], arr[i + 1]
  return i + 1

def quicksort(arr, inicio, fin):
  if inicio >= fin:
    return
  p = particion_lomuto_mediana(arr, inicio, fin)
  quicksort(arr, inicio, p - 1)
  quicksort(arr, p + 1, fin)

datos = [29, 10, 14, 37, 13, 5, 88, 1]
quicksort(datos, 0, len(datos) - 1)
print(datos)

Con esta base puedes intercambiar el esquema de pivote o la función de partición sin cambiar la interfaz pública.