Quick sort y selección del pivote
Construya quick sort con los esquemas de partición de Lomuto y Hoare, analice el peor caso O(n²) y cómo lo mitiga la selección aleatoria del pivote.
Quick sort y selección del pivote es una lección gratuita de Coding Interview Prep en CoddyKit. Esta es la lección 3 de 4. Puedes leer la lección completa abajo gratuitamente — luego la practicas en el navegador con un editor de código integrado y un tutor de IA 24/7. Forma parte de la ruta de aprendizaje de Coding Interview Prep, y tu progreso se sincroniza en la web y la app de CoddyKit. El curso de Coding Interview Prep incluye 4 lecciones en total.
Quick Sort: Divide y vencerás in-place
Quick sort es el algoritmo de ordenamiento más utilizado en la práctica. A diferencia de merge sort, ordena in-place sin asignar arreglos adicionales. La idea central es elegir un elemento pivote, particionar el arreglo de modo que todos los elementos menores que el pivote queden antes que él y todos los mayores queden después, y luego ordenar recursivamente cada partición. El paso de partición toma un tiempo O(n) y, con un buen pivote, la profundidad de la recursión es O(log n).
def quick_sort(arr, lo=0, hi=None):
if hi is None: hi = len(arr) - 1
if lo < hi:
pivot_idx = partition(arr, lo, hi)
quick_sort(arr, lo, pivot_idx - 1) # sort left
quick_sort(arr, pivot_idx + 1, hi) # sort right
def partition(arr, lo, hi):
pivot = arr[hi] # Lomuto: choose last element as pivot
i = lo - 1
for j in range(lo, hi):
if arr[j] <= pivot:
i += 1
arr[i], arr[j] = arr[j], arr[i]
arr[i+1], arr[hi] = arr[hi], arr[i+1]
return i + 1
arr = [3, 6, 8, 10, 1, 2, 1]
quick_sort(arr)
print(arr) # [1, 1, 2, 3, 6, 8, 10]Esquema de partición de Lomuto
La partición de Lomuto usa el último elemento como pivote. Un puntero lento i registra el límite de la región de elementos 'menores que el pivote'; un puntero rápido j avanza por el arreglo. Cuando arr[j] <= pivot, incremente i e intercambie arr[i] con arr[j] para ampliar la región de elementos pequeños. Después del recorrido, coloque el pivote en i+1 intercambiándolo con arr[hi]. Es sencillo de implementar, pero realiza 3× más intercambios que el esquema de Hoare.
def lomuto_partition_traced(arr, lo, hi):
pivot = arr[hi]
i = lo - 1
print(f'Pivot: {pivot}, array: {arr[lo:hi+1]}')
for j in range(lo, hi):
if arr[j] <= pivot:
i += 1
arr[i], arr[j] = arr[j], arr[i]
arr[i+1], arr[hi] = arr[hi], arr[i+1]
print(f'After partition: {arr[lo:hi+1]}')
return i + 1
arr = [3, 1, 4, 1, 5, 9, 2, 6]
lomuto_partition_traced(arr, 0, len(arr)-1)Esquema de partición de Hoare
La partición de Hoare usa dos punteros que comienzan en ambos extremos y avanzan hacia el centro hasta cruzarse. Elige el pivote (normalmente el primer elemento) y mueve los elementos menores que el pivote hacia la izquierda y los mayores hacia la derecha. El esquema de Hoare realiza 3× menos intercambios que Lomuto y funciona mejor con elementos iguales, pero el pivote no termina en su posición final después de la partición, lo que requiere llamadas recursivas ligeramente distintas.
def hoare_partition(arr, lo, hi):
pivot = arr[lo] # first element as pivot
i, j = lo - 1, hi + 1
while True:
i += 1
while arr[i] < pivot: i += 1
j -= 1
while arr[j] > pivot: j -= 1
if i >= j: return j
arr[i], arr[j] = arr[j], arr[i]
def quick_sort_hoare(arr, lo=0, hi=None):
if hi is None: hi = len(arr) - 1
if lo < hi:
p = hoare_partition(arr, lo, hi)
quick_sort_hoare(arr, lo, p) # note: p not p-1
quick_sort_hoare(arr, p+1, hi)
arr = [3, 6, 8, 10, 1, 2, 1]
quick_sort_hoare(arr)
print(arr) # [1, 1, 2, 3, 6, 8, 10]Peor caso O(n²): entrada ya ordenada
El peor caso de quick sort se produce cuando el pivote es sistemáticamente el elemento más pequeño o más grande de la partición. Con el pivote en el último elemento de Lomuto sobre un arreglo ya ordenado, la partición siempre coloca 0 elementos a la izquierda y n-1 a la derecha: el árbol de recursión se degenera en una cadena de profundidad n, lo que produce O(n²) comparaciones. Por eso la selección del pivote es crucial y las implementaciones de producción aleatorizan el pivote.
import sys
sys.setrecursionlimit(5000)
def quick_sort_naive(arr, lo=0, hi=None):
if hi is None: hi = len(arr) - 1
comparisons = [0]
def _qs(lo, hi):
if lo >= hi: return
pivot = arr[hi] # last element pivot
i = lo - 1
for j in range(lo, hi):
comparisons[0] += 1
if arr[j] <= pivot:
i += 1; arr[i], arr[j] = arr[j], arr[i]
arr[i+1], arr[hi] = arr[hi], arr[i+1]
p = i + 1
_qs(lo, p-1); _qs(p+1, hi)
_qs(lo, hi)
return comparisons[0]
import math
n = 100
sorted_arr = list(range(n))
ops = quick_sort_naive(sorted_arr)
print(f'n={n}, ops={ops}, n^2={n**2}') # ops close to n*(n-1)/2Pivote aleatorio: O(n log n) esperado
Al elegir el pivote uniformemente al azar (intercambie un elemento aleatorio con arr[hi] antes de particionar), la probabilidad de elegir pivotes malos de forma sistemática disminuye exponencialmente. El número esperado de comparaciones es 2n ln(n) ≈ 1.39 n log₂(n), lo que produce un tiempo esperado O(n log n) con una probabilidad abrumadoramente alta. Por eso se usa quick sort aleatorio en la práctica: evita casos extremos que un adversario podría crear para estrategias con pivote fijo.
import random
def quick_sort_random(arr, lo=0, hi=None):
if hi is None: hi = len(arr) - 1
if lo < hi:
# Randomise pivot
rand_i = random.randint(lo, hi)
arr[rand_i], arr[hi] = arr[hi], arr[rand_i]
# Lomuto partition with last element as pivot
pivot = arr[hi]
i = lo - 1
for j in range(lo, hi):
if arr[j] <= pivot:
i += 1; arr[i], arr[j] = arr[j], arr[i]
arr[i+1], arr[hi] = arr[hi], arr[i+1]
p = i + 1
quick_sort_random(arr, lo, p - 1)
quick_sort_random(arr, p + 1, hi)
arr = list(range(100, 0, -1)) # worst case for naive
quick_sort_random(arr)
print(arr[:10]) # [1,2,3,4,5,6,7,8,9,10]Pivote de la mediana de tres
Otra estrategia para elegir el pivote consiste en seleccionar la mediana del primer elemento, el elemento central y el último elemento. Esto evita el comportamiento del peor caso con entradas ordenadas o ordenadas en sentido inverso (las entradas adversarias más comunes), sin añadir el costo de generar números aleatorios. Muchas implementaciones de producción usan la mediana de tres o ninther (la mediana de tres medianas) para arreglos grandes y cambian a insertion sort para subarreglos pequeños, por debajo de un umbral de ~10 elementos.
def median_of_three(arr, lo, hi):
mid = (lo + hi) // 2
# Sort lo, mid, hi values in place
if arr[lo] > arr[mid]: arr[lo], arr[mid] = arr[mid], arr[lo]
if arr[lo] > arr[hi]: arr[lo], arr[hi] = arr[hi], arr[lo]
if arr[mid] > arr[hi]: arr[mid], arr[hi] = arr[hi], arr[mid]
# Median is now at arr[mid]; swap to arr[hi-1] as pivot
arr[mid], arr[hi] = arr[hi], arr[mid]
return arr[hi] # pivot value
arr = [3, 9, 1]
print(median_of_three(arr, 0, 2), arr) # 3, [1,3,9] (sorted)Bandera nacional neerlandesa: partición de tres vías
La partición estándar coloca los elementos menores que el pivote a la izquierda y los mayores a la derecha, pero los elementos iguales al pivote quedan dispersos. La partición de tres vías (bandera nacional neerlandesa) crea tres regiones: <pivot, ==pivot, >pivot. Esto es crucial para arreglos con muchos duplicados, en los que el quick sort estándar se degrada a O(n²), mientras que el quick sort de tres vías alcanza O(n) con entradas cuyos valores son todos iguales.
def three_way_partition(arr, lo, hi):
pivot = arr[lo]
lt = lo # arr[lo..lt-1] < pivot
gt = hi # arr[gt+1..hi] > pivot
i = lo # current
while i <= gt:
if arr[i] < pivot:
arr[lt], arr[i] = arr[i], arr[lt]
lt += 1; i += 1
elif arr[i] > pivot:
arr[i], arr[gt] = arr[gt], arr[i]
gt -= 1 # don't advance i
else:
i += 1
return lt, gt # pivot occupies arr[lt..gt]
arr = [3, 1, 4, 1, 5, 9, 2, 6, 3, 3]
lt, gt = three_way_partition(arr, 0, len(arr)-1)
print(arr, '| pivot region:', lt, 'to', gt)Quickselect: k-ésimo elemento menor en O(n)
Quickselect usa el paso de partición de quick sort para encontrar el k-ésimo elemento menor en un tiempo promedio O(n), sin ordenar completamente. Después de particionar, el pivote está en su posición final p. Si p == k, devuelva arr[p]. Si k < p, haga la llamada recursiva sobre la partición izquierda; si k > p, hágala sobre la derecha. En promedio, cada nivel de recursión divide el problema por la mitad: O(n) + O(n/2) + O(n/4) + ... = O(2n) = O(n).
import random
def quickselect(nums, k):
'''Find kth smallest (0-indexed) in O(n) average.'''
def _select(lo, hi):
if lo == hi: return nums[lo]
rand_i = random.randint(lo, hi)
nums[rand_i], nums[hi] = nums[hi], nums[rand_i]
pivot = nums[hi]
i = lo - 1
for j in range(lo, hi):
if nums[j] <= pivot:
i += 1; nums[i], nums[j] = nums[j], nums[i]
p = i + 1
nums[p], nums[hi] = nums[hi], nums[p]
if p == k: return nums[p]
elif k < p: return _select(lo, p - 1)
else: return _select(p + 1, hi)
return _select(0, len(nums) - 1)
print(quickselect([3,2,1,5,6,4], 1)) # 2 (2nd smallest)Complejidad espacial de Quick Sort
Quick sort se denomina 'in-place', pero utiliza un espacio de pila promedio O(log n) para la recursión (un marco por cada nivel del árbol de recursión). En el peor caso, la profundidad de la pila es O(n). Para garantizar un espacio de pila O(log n) en el peor caso, realice siempre la llamada recursiva sobre la partición más pequeña primero y use la optimización de llamadas de cola para la partición más grande. El límite de recursión de Python hace que las recursiones muy profundas de quick sort sean arriesgadas; conviene mencionarlo en las entrevistas.
def quick_sort_optimised(arr, lo=0, hi=None):
if hi is None: hi = len(arr) - 1
while lo < hi:
p = lomuto_partition_qs(arr, lo, hi)
# Recurse on smaller partition; iterate on larger
if p - lo < hi - p:
quick_sort_optimised(arr, lo, p - 1)
lo = p + 1 # tail-call elimination
else:
quick_sort_optimised(arr, p + 1, hi)
hi = p - 1
def lomuto_partition_qs(arr, lo, hi):
pivot = arr[hi]; i = lo - 1
for j in range(lo, hi):
if arr[j] <= pivot: i += 1; arr[i], arr[j] = arr[j], arr[i]
arr[i+1], arr[hi] = arr[hi], arr[i+1]
return i + 1Comparación de algoritmos de ordenamiento
Integre sus conocimientos:
- Quick sort: O(n log n) esperado, O(n²) en el peor caso, espacio O(log n), inestable, más rápido en la práctica con datos aleatorios
- Merge sort: O(n log n) garantizado, espacio O(n), estable, ideal para listas enlazadas y ordenamiento externo
- Heap sort: O(n log n) garantizado, espacio O(1), inestable, más lento en la práctica debido a los fallos de caché
- Insertion sort: O(n) en el mejor caso, ideal para n pequeño o datos casi ordenados
# Python's sorted() uses Timsort:
# - Hybrid: merge sort for large runs, insertion sort for small (< 64 elements)
# - Stable, O(n log n) worst case
# - O(n) best case for sorted/reverse-sorted/nearly-sorted
# - O(n) extra space
import random
arr = random.sample(range(10000), 1000)
sorted_arr = sorted(arr) # Timsort
print(sorted_arr[:5], '...') # first 5 elementsIntrosort: combinación de los tres
Introsort (usado en std::sort de C++ STL) combina quick sort, heap sort e insertion sort: comienza con quick sort aleatorio; si la profundidad de la recursión supera 2 log n (lo que indica una secuencia de pivotes malos), cambia a heap sort para garantizar O(n log n); y usa insertion sort para subarreglos de menos de 16 elementos. Esto ofrece un peor caso O(n log n), la velocidad de quick sort en el caso promedio y la eficiencia de insertion sort para subarreglos pequeños.
# Introsort hybrid (simplified)
def introsort(arr, depth_limit=None):
if depth_limit is None:
import math
depth_limit = 2 * int(math.log2(len(arr) + 1)) if arr else 0
if len(arr) <= 16:
# insertion sort for small arrays
for i in range(1, len(arr)):
key = arr[i]; j = i - 1
while j >= 0 and arr[j] > key:
arr[j+1] = arr[j]; j -= 1
arr[j+1] = key
return arr
if depth_limit == 0:
arr.sort() # fall back to heapsort equivalent
return arr
# Otherwise quick sort
pivot = arr[-1]
small = [x for x in arr[:-1] if x <= pivot]
large = [x for x in arr[:-1] if x > pivot]
return introsort(small, depth_limit-1) + [pivot] + introsort(large, depth_limit-1)
print(introsort([5,3,8,1,9,2,7]))Comprobación rápida
Compruebe su comprensión de los conceptos de Data Structures & Algorithms — Coding Interview Prep de esta lección.
Recapitulación de la lección
En esta lección aprendió que: quick sort particiona el arreglo in-place alrededor de un pivote y realiza llamadas recursivas a cada lado, logrando un tiempo esperado O(n log n) con un espacio de pila O(log n), y es más rápido en la práctica que merge sort con datos aleatorios; el peor caso O(n²) ocurre con entradas ordenadas y un pivote fijo, y se evita mediante la selección aleatoria del pivote o la mediana de tres; y la partición de tres vías maneja los elementos duplicados de forma eficiente, mientras que quickselect amplía la idea de la partición para encontrar el k-ésimo elemento menor en un tiempo promedio O(n) sin ordenar completamente. A continuación exploraremos los ordenamientos que no se basan en comparaciones y el ordenamiento integrado de Python.
Preguntas frecuentes
¿La lección «Quick sort y selección del pivote» es gratis?
Sí — el texto completo de «Quick sort y selección del pivote» es gratis para leer aquí en la web. Para practicarla de forma interactiva (editor de código integrado y tutor de IA 24/7) y desbloquear el resto del curso de Coding Interview Prep, actualiza a CoddyKit PRO. El curso de Coding Interview Prep incluye 4 lecciones en total.
¿Qué aprenderé en «Quick sort y selección del pivote»?
Construya quick sort con los esquemas de partición de Lomuto y Hoare, analice el peor caso O(n²) y cómo lo mitiga la selección aleatoria del pivote. Practicas Coding Interview Prep con código real que ejecutas directamente en el navegador, y un tutor de IA 24/7 responde tus preguntas mientras trabajas en la lección.
¿Necesito experiencia previa para empezar Coding Interview Prep?
No se requiere experiencia previa. Coding Interview Prep en CoddyKit está estructurado para principiantes hasta estudiantes avanzados, así que puedes empezar aquí o desde el inicio y avanzar a tu ritmo. Esta es la lección 3 de 4.
¿Cuánto tiempo toma la lección «Quick sort y selección del pivote»?
La mayoría de las lecciones de CoddyKit toman alrededor de 5–10 minutos. Cada una es compacta e interactiva, así que avanzas constantemente y retomas exactamente por donde dejaste en la web y la app.
¿Puedo escribir y ejecutar código en esta lección de Coding Interview Prep?
Sí. Cada lección de Coding Interview Prep incluye un editor de código integrado, así que escribes y ejecutas código real directamente en tu navegador y obtienes retroalimentación instantánea de IA — sin configuración local necesaria.
Todas las lecciones de este curso
- Bubble sort e insertion sort
- Merge sort: dividir, ordenar y combinar
- Quick sort y selección del pivote
- Ordenaciones sin comparación y sort() de Python