Quick Sort
Última actualización
Quicksort es un algoritmo de divide y vencerás que ordena en torno a un "pivote". Elige un elemento pivote y luego particiona el arreglo de modo que todo lo menor quede antes y todo lo mayor quede después, lo que fija el pivote en su posición final ordenada. Después recurre sobre las particiones izquierda y derecha. Esta visualización usa el esquema de Lomuto con el último elemento como pivote. Pulsa reproducir para ver la partición y la colocación del pivote.
Quicksort suele ser el ordenamiento de propósito general más rápido en la práctica gracias a su buen comportamiento de caché y a la partición en el mismo lugar, con un promedio de O(n log n). Su peor caso es O(n²) (por ejemplo, un arreglo ya ordenado con una mala elección de pivote), que estrategias de pivote como la mediana de tres o la aleatorización evitan.
Complejidad temporal y espacial
| Caso | Complejidad | Notas |
|---|---|---|
| Mejor caso | O(n log n) | Particiones equilibradas |
| Caso promedio | O(n log n) | Orden aleatorio |
| Peor caso | O(n²) | Pivotes desequilibrados de forma constante |
| Espacio | O(log n) | Pila de recursión (partición en el mismo lugar) |
| Estable | No | Los intercambios de partición reordenan elementos iguales |
Paso a paso
| Paso | Qué ocurre |
|---|---|
| 1 | Elige un pivote (aquí, el último elemento del rango). |
| 2 | Partición: mueve a su izquierda todos los elementos menores que el pivote. |
| 3 | Intercambia el pivote a la frontera: ahora está en su posición final. |
| 4 | Aplica quicksort recursivamente a la partición izquierda. |
| 5 | Aplica quicksort recursivamente a la partición derecha. |
Ejemplo resuelto
Ordenando [5, 2, 4, 1] con el esquema de Lomuto (último elemento como pivote):
| Pasada | Arreglo | Acción |
|---|---|---|
| Inicio | [5, 2, 4, 1] | Particiona todo el rango; el pivote es 1 (último elemento). |
| 1 | [1, 2, 4, 5] | Nada es menor que 1, así que intercambia 1 al índice 0; el pivote 1 queda final. Recurre a la derecha sobre [2, 4, 5]. |
| 2 | [1, 2, 4, 5] | Particiona [2, 4, 5] con pivote 5; tanto 2 como 4 son menores, así que 5 se queda al final y queda final. Recurre a la izquierda sobre [2, 4]. |
| 3 | [1, 2, 4, 5] | Particiona [2, 4] con pivote 4; 2 es menor, así que 4 se queda en su sitio y queda final. 2 es un solo elemento, así que ya está ordenado. |
| Fin | [1, 2, 4, 5] | Cada pivote queda fijado en su lugar; el arreglo está ordenado. |
Cuándo usar quicksort
| Úsalo cuando | Evítalo cuando |
|---|---|
| Necesitas un ordenamiento en memoria rápido y de propósito general con constantes pequeñas. | Necesitas garantía de tiempo O(n log n) en el peor caso (usa heap sort o merge sort). |
La memoria es escasa: la partición es en el mismo lugar y solo necesita O(log n) de pila. | Necesitas un ordenamiento estable que preserve el orden de las claves iguales. |
| Los datos están en orden aleatorio o desconocido y usas un pivote aleatorio o mediana de tres. | La entrada ya está ordenada o casi ordenada y el pivote es fijo, disparando O(n²). |
| Importa la localidad de caché, ya que quicksort accede a la memoria de forma secuencial. | Ordenas una lista enlazada, donde merge sort evita el acceso aleatorio del que depende quicksort. |
Código de Quick Sort
Una implementación limpia y ejecutable de Quick Sort en Python, JavaScript, Java, C++, C. Elige un lenguaje, copia el código o ábrelo ya cargado en el Playground de Coddy.
Código de Quick Sort en Python
Python
1def quick_sort(a, low=0, high=None):2 if high is None:3 high = len(a) - 14 if low < high:5 p = partition(a, low, high)6 quick_sort(a, low, p - 1)7 quick_sort(a, p + 1, high)8 return a9
10
11def partition(a, low, high):12 # Lomuto partition: everything < pivot moves left of it13 pivot = a[high]14 i = low15 for j in range(low, high):16 if a[j] < pivot:17 a[i], a[j] = a[j], a[i]18 i += 119 a[i], a[high] = a[high], a[i]20 return i21
22
23nums = [10, 7, 8, 9, 1, 5]24print("Before:", nums)25quick_sort(nums)26print("After: ", nums)Código de Quick Sort en JavaScript
JavaScript
1function quickSort(a, lo = 0, hi = a.length - 1) {2 if (lo >= hi) return a;3 const p = partition(a, lo, hi);4 quickSort(a, lo, p - 1);5 quickSort(a, p + 1, hi);6 return a;7}8
9// Lomuto partition: last element is the pivot10function partition(a, lo, hi) {11 const pivot = a[hi];12 let i = lo;13 for (let j = lo; j < hi; j++) {14 if (a[j] < pivot) {15 [a[i], a[j]] = [a[j], a[i]];16 i++;17 }18 }19 [a[i], a[hi]] = [a[hi], a[i]];20 return i;21}22
23const data = [5, 2, 9, 1, 7, 3];24console.log("Before:", data);25console.log("Sorted:", quickSort([...data]));Código de Quick Sort en Java
Java
1import java.util.Arrays;2
3public class Main {4 static void quickSort(int[] arr, int low, int high) {5 if (low >= high) return;6 int p = partition(arr, low, high);7 quickSort(arr, low, p - 1);8 quickSort(arr, p + 1, high);9 }10
11 // Lomuto partition: last element is the pivot12 static int partition(int[] arr, int low, int high) {13 int pivot = arr[high];14 int i = low - 1;15 for (int j = low; j < high; j++) {16 if (arr[j] < pivot) swap(arr, ++i, j);17 }18 swap(arr, i + 1, high);19 return i + 1;20 }21
22 static void swap(int[] arr, int a, int b) {23 int tmp = arr[a];24 arr[a] = arr[b];25 arr[b] = tmp;26 }27
28 public static void main(String[] args) {29 int[] arr = {10, 7, 8, 9, 1, 5};30 System.out.println("Before: " + Arrays.toString(arr));31 quickSort(arr, 0, arr.length - 1);32 System.out.println("After: " + Arrays.toString(arr));33 }34}Código de Quick Sort en C++
C++
1#include <iostream>2#include <utility>3#include <vector>4
5void printVec(const std::vector<int>& a) {6 for (int x : a) std::cout << x << " ";7 std::cout << "\n";8}9
10// Lomuto partition: place the pivot in its final position11int partition(std::vector<int>& a, int lo, int hi) {12 int pivot = a[hi];13 int i = lo;14 for (int j = lo; j < hi; ++j) {15 if (a[j] < pivot) std::swap(a[i++], a[j]);16 }17 std::swap(a[i], a[hi]);18 return i;19}20
21void quickSort(std::vector<int>& a, int lo, int hi) {22 if (lo >= hi) return;23 int p = partition(a, lo, hi);24 quickSort(a, lo, p - 1);25 quickSort(a, p + 1, hi);26}27
28int main() {29 std::vector<int> data = {10, 7, 8, 9, 1, 5};30 std::cout << "Before: ";31 printVec(data);32 quickSort(data, 0, static_cast<int>(data.size()) - 1);33 std::cout << "After: ";34 printVec(data);35 return 0;36}Código de Quick Sort en C
C
1#include <stdio.h>2
3void printArr(const int a[], int n) {4 for (int i = 0; i < n; i++) printf("%d ", a[i]);5 printf("\n");6}7
8void swap(int* x, int* y) {9 int tmp = *x;10 *x = *y;11 *y = tmp;12}13
14// Lomuto partition: place the pivot in its final position15int partition(int a[], int lo, int hi) {16 int pivot = a[hi];17 int i = lo;18 for (int j = lo; j < hi; j++) {19 if (a[j] < pivot) swap(&a[i++], &a[j]);20 }21 swap(&a[i], &a[hi]);22 return i;23}24
25void quickSort(int a[], int lo, int hi) {26 if (lo >= hi) return;27 int p = partition(a, lo, hi);28 quickSort(a, lo, p - 1);29 quickSort(a, p + 1, hi);30}31
32int main(void) {33 int data[] = {10, 7, 8, 9, 1, 5};34 int n = sizeof(data) / sizeof(data[0]);35 printf("Before: ");36 printArr(data, n);37 quickSort(data, 0, n - 1);38 printf("After: ");39 printArr(data, n);40 return 0;41}Preguntas frecuentes sobre Quick Sort
¿Cuál es la complejidad temporal de quicksort?
Quicksort promedia
O(n log n) y es O(n log n) en el mejor caso, pero degenera a O(n²) en el peor caso cuando las particiones están constantemente desequilibradas. Los pivotes aleatorios o de mediana de tres hacen muy improbable el peor caso.¿Es quicksort estable?
No. La partición estándar en el mismo lugar intercambia elementos distantes, lo que puede cambiar el orden relativo de claves iguales. Existen variantes estables, pero renuncian a la ventaja de quicksort de operar en el mismo lugar.
¿Por qué quicksort suele ser más rápido que merge sort?
Quicksort particiona en el mismo lugar con excelente localidad de caché y sin búfer adicional, por lo que sus constantes son pequeñas. Merge sort iguala su cota
O(n log n) pero paga un búfer de O(n) y más movimiento de datos.Quicksort vs merge sort: ¿cuál debería usar?
Elige quicksort para ordenar arreglos en memoria de forma rápida y en el mismo lugar, donde sus constantes pequeñas suelen ganar. Elige merge sort cuando necesites un ordenamiento estable, garantía de peor caso
O(n log n), o cuando ordenes listas enlazadas o datos externos que no caben en RAM.¿Por qué quicksort se vuelve O(n²) en un arreglo ordenado?
Con un pivote fijo como el primer o último elemento, una entrada ya ordenada hace que cada partición separe solo un elemento, produciendo
n niveles de recursión en vez de log n. Elegir el pivote de forma aleatoria o con mediana de tres rompe este patrón y restaura el comportamiento O(n log n).¿Cuál es la diferencia entre los esquemas de partición de Lomuto y Hoare?
El esquema de Lomuto usa un único índice que recorre de izquierda a derecha y es más simple de codificar, por eso esta visualización lo emplea. El esquema de Hoare usa dos punteros que avanzan hacia el interior y suele hacer menos intercambios, siendo más rápido en la práctica, pero no coloca el pivote en su posición final durante el paso de partición.
Recursos relacionados
Más visualizaciones
