Quicksort
Divide y vencerás
Quicksort es una lección gratuita de C Academy en CoddyKit. Esta es la lección 2 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 C Academy, y tu progreso se sincroniza en la web y la app de CoddyKit. El curso de C Academy incluye 4 lecciones en total.
Divide y vencerás
Quicksort es un algoritmo de ordenación basado en divide y vencerás. Elige un pivote, particiona el arreglo para que los elementos menores queden a la izquierda y los mayores a la derecha, y después ordena recursivamente cada lado.
El tiempo medio es O(n log n).
El paso de particionado
La idea clave es el particionado: reorganizar el arreglo alrededor de un pivote para que todo lo que queda a su izquierda sea menor y todo lo que queda a su derecha sea mayor. El pivote queda entonces en su posición final ordenada.
Esquema de particionado de Lomuto
El esquema de Lomuto utiliza el último elemento como pivote. Mantiene un índice i para el límite de los elementos menores y realiza intercambios mientras recorre el arreglo.
#include <stdio.h>
int partition(int a[], int lo, int hi) {
int pivot = a[hi], i = lo - 1;
for (int j = lo; j < hi; j++)
if (a[j] < pivot) {
i++;
int t = a[i]; a[i] = a[j]; a[j] = t;
}
int t = a[i+1]; a[i+1] = a[hi]; a[hi] = t;
return i + 1;
}
int main(void) {
int a[] = {5, 2, 9, 1, 3};
int p = partition(a, 0, 4);
printf("pivot index = %d\n", p);
for (int i = 0; i < 5; i++) printf("%d ", a[i]);
printf("\n");
return 0;
}La ordenación recursiva
Quicksort llama al particionado y después aplica recursión a los dos subarreglos situados a cada lado del pivote. El caso base es un subarreglo de tamaño 0 o 1.
#include <stdio.h>
int partition(int a[], int lo, int hi) {
int pivot = a[hi], i = lo - 1;
for (int j = lo; j < hi; j++)
if (a[j] < pivot) { i++; int t=a[i];a[i]=a[j];a[j]=t; }
int t = a[i+1]; a[i+1] = a[hi]; a[hi] = t;
return i + 1;
}
void quicksort(int a[], int lo, int hi) {
if (lo < hi) {
int p = partition(a, lo, hi);
quicksort(a, lo, p - 1);
quicksort(a, p + 1, hi);
}
}
int main(void) {
int a[] = {9, 3, 7, 1, 8, 2, 5};
quicksort(a, 0, 6);
for (int i = 0; i < 7; i++) printf("%d ", a[i]);
printf("\n");
return 0;
}Elegir un buen pivote
Un pivote deficiente (por ejemplo, elegir siempre el último elemento con una entrada ordenada) provoca un comportamiento O(n²). Las mejores opciones distribuyen las particiones de forma más uniforme.
- Mediana de tres
- Pivote aleatorio
Mediana de tres
La mediana de tres elige como pivote la mediana del primer, el central y el último elemento, evitando el comportamiento del peor caso con datos ya ordenados.
#include <stdio.h>
int median_of_three(int a[], int lo, int hi) {
int mid = lo + (hi - lo) / 2;
if (a[mid] < a[lo]) { int t=a[mid];a[mid]=a[lo];a[lo]=t; }
if (a[hi] < a[lo]) { int t=a[hi];a[hi]=a[lo];a[lo]=t; }
if (a[hi] < a[mid]) { int t=a[hi];a[hi]=a[mid];a[mid]=t; }
return mid;
}
int main(void) {
int a[] = {7, 1, 5, 3, 9};
int m = median_of_three(a, 0, 4);
printf("median value = %d\n", a[m]);
return 0;
}Análisis del peor caso
Si cada partición separa solo un elemento, la profundidad de la recursión alcanza n y el coste es O(n²). Esto ocurre con un pivote fijo cuando la entrada está ordenada o en orden inverso.
La aleatorización hace que el peor caso sea extremadamente improbable.
Pivote aleatorio
Intercambiar un elemento aleatorio con la posición del pivote antes de particionar protege frente a entradas adversarias.
#include <stdio.h>
#include <stdlib.h>
int main(void) {
int a[] = {1, 2, 3, 4, 5};
int lo = 0, hi = 4;
srand(42);
int r = lo + rand() % (hi - lo + 1);
int t = a[r]; a[r] = a[hi]; a[hi] = t; /* move random to pivot slot */
printf("chosen pivot = %d\n", a[hi]);
return 0;
}En el propio arreglo y no estable
Quicksort ordena en el propio arreglo utilizando, en promedio, solo O(log n) de espacio en la pila. Sin embargo, no es estable: los elementos iguales pueden cambiar de orden debido a los intercambios del particionado.
Optimización de llamadas finales
Aplicar la recursión primero a la mitad más pequeña y usar un bucle para la mitad más grande limita la profundidad de la pila a O(log n), evitando el desbordamiento de la pila con arreglos grandes.
Ordenación de cadenas
La misma estructura permite ordenar cualquier tipo cuyos elementos puedan compararse. Aquí quicksort ordena un arreglo de enteros, pero basta con cambiar la comparación para admitir otros tipos.
#include <stdio.h>
int partition(int a[], int lo, int hi) {
int pivot = a[hi], i = lo - 1;
for (int j = lo; j < hi; j++)
if (a[j] < pivot) { i++; int t=a[i];a[i]=a[j];a[j]=t; }
int t = a[i+1]; a[i+1] = a[hi]; a[hi] = t; return i + 1;
}
void quicksort(int a[], int lo, int hi) {
if (lo < hi) { int p = partition(a, lo, hi); quicksort(a, lo, p-1); quicksort(a, p+1, hi); }
}
int main(void) {
int a[] = {42, -7, 0, 100, 13, 13};
quicksort(a, 0, 5);
for (int i = 0; i < 6; i++) printf("%d ", a[i]);
printf("\n");
return 0;
}Comprobación rápida
Compruebe su comprensión de quicksort.
Resumen
Ha aprendido quicksort.
- Particione alrededor de un pivote y después aplique recursión a cada lado
- O(n log n) en promedio y O(n²) en el peor caso
- La mediana de tres o los pivotes aleatorios evitan el peor caso
- Ordena en el propio arreglo, pero no es estable
Preguntas frecuentes
¿La lección «Quicksort» es gratis?
Sí — el texto completo de «Quicksort» 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 C Academy, actualiza a CoddyKit PRO. El curso de C Academy incluye 4 lecciones en total.
¿Qué aprenderé en «Quicksort»?
Divide y vencerás Practicas C Academy 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 C Academy?
No se requiere experiencia previa. C Academy 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 2 de 4.
¿Cuánto tiempo toma la lección «Quicksort»?
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 C Academy?
Sí. Cada lección de C Academy 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.