Edición didáctica en español. El código y sus salidas conservan el original.
Quicksort en C
Ordena un array mediante partición y recursión; comprende el pivote y los casos desfavorables.
Quicksort elige un pivote y reorganiza los elementos para separar valores menores y mayores. Después ordena recursivamente cada parte. En la partición de Lomuto del ejemplo, el último elemento sirve de pivote y un índice delimita la región ya procesada.
El caso base detiene la recursión cuando el intervalo contiene menos de dos elementos. El tiempo medio es O(N log N), pero puede llegar a O(N²) con particiones muy desequilibradas. También cuenta el espacio de la pila recursiva; no lo confundas con la ausencia de un segundo array.
Prueba valores repetidos, un array ya ordenado y uno en orden inverso. Revisa los límites antes de cada llamada y no supongas que esta implementación conserva el orden original de elementos iguales.
Código C
#include <stdio.h>
void swap(int *a, int *b) {
int t = *a;
*a = *b;
*b = t;
}
int partition(int arr[], int low, int high) {
int pivot = arr[high];
int i = (low - 1);
for (int j = low; j < high; j++) {
if (arr[j] <= pivot) {
i++;
swap(&arr[i], &arr[j]);
}
}
swap(&arr[i + 1], &arr[high]);
return (i + 1);
}
void quickSort(int arr[], int low, int high) {
if (low < high) {
int pi = partition(arr, low, high);
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
int main() {
int arr[] = {10, 80, 30, 90, 40, 50, 70};
int n = sizeof(arr) / sizeof(arr[0]);
quickSort(arr, 0, n - 1);
printf("Sorted array:\n");
for (int i = 0; i < n; i++) printf("%d ", arr[i]);
printf("\n");
return 0;
}Salida esperada
Sorted array: 10 30 40 50 70 80 90
Preguntas frecuentes
¿Por qué el código y la salida siguen en inglés?
Las palabras clave, los identificadores y los textos que verifican las pruebas se conservan para no cambiar el programa. Las explicaciones y los controles están traducidos.