Ordenación
La ordenación es el proceso de reorganizar un conjunto de datos en un orden específico; es uno de los problemas algorítmicos más básicos y más estudiados en el procesamiento de datos.
Familia de algoritmos de ordenación
Ordenación básica (O(n²))
La ordenación de burbuja, la ordenación por selección y la ordenación por inserción son simples de implementar y adecuadas para datos a pequeña escala o para fines didácticos.
Ordenación avanzada (O(n log n))
La ordenación rápida, la ordenación por fusión y la ordenación por montículos son las más utilizadas en ingeniería. La ordenación de Shell es una mejora de la ordenación por inserción.
Ejemplos
void swap(int* a, int* b) { int t = *a; *a = *b; *b = t; }
/* Ordenación de burbuja — O(n²), estable
Cada ronda "hace burbujear" el elemento más grande hasta el final */
void bubbleSort(int arr[], int n) {
for (int i = 0; i < n - 1; i++) {
int swapped = 0; /* Optimización: terminación anticipada */
for (int j = 0; j < n - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
swap(&arr[j], &arr[j + 1]);
swapped = 1;
}
}
if (!swapped) break; /* Ya está ordenado, finalizar antes */
}
}
/* Función de partición de ordenación rápida — O(n log n) promedio, inestable
Elegir el pivote; los menores que pivot van a la izquierda, los mayores a la derecha */
int partition(int arr[], int low, int high) {
int pivot = arr[high]; /* Elegir el último elemento como pivote */
int i = low - 1; /* i apunta al final de la región menor que pivot */
for (int j = low; j < high; j++) {
if (arr[j] < pivot) {
i++;
swap(&arr[i], &arr[j]);
}
}
swap(&arr[i + 1], &arr[high]); /* Colocar el pivote en la posición correcta */
return i + 1;
}
void quickSort(int arr[], int low, int high) {
if (low < high) {
int pi = partition(arr, low, high); /* Índice de partición */
quickSort(arr, low, pi - 1); /* Ordenar recursivamente la mitad izquierda */
quickSort(arr, pi + 1, high); /* Ordenar recursivamente la mitad derecha */
}
}
void printArray(int arr[], int n) {
for (int i = 0; i < n; i++) printf("%d ", arr[i]);
printf("\n");
}
int main() {
int arr1[] = {64, 34, 25, 12, 22, 11, 90};
int n1 = 7;
bubbleSort(arr1, n1);
printf("Ordenación de burbuja: "); printArray(arr1, n1);
/* Salida: 11 12 22 25 34 64 90 */
int arr2[] = {64, 34, 25, 12, 22, 11, 90};
quickSort(arr2, 0, 6);
printf("Ordenación rápida: "); printArray(arr2, 7);
/* Salida: 11 12 22 25 34 64 90 */
return 0;
}
Ilustración del pensamiento divide y vencerás
Ordenación rápida (partición)
Elegir el pivote
Menores que el pivote → izquierda, mayores → derecha
Ordenar recursivamente los subarreglos izquierdo y derecho
Inestable | In situ | La más utilizada
Ordenación por fusión (combinación)
Dividir recursivamente por la mitad hasta la unidad más pequeña
Combinar dos subsecuencias ordenadas
Requiere un arreglo adicional O(n)
Estable | Requiere espacio adicional | Ordenación externa
Ordenación por montículos (heapify)
Construir un montículo máximo O(n)
Colocar la cima del montículo (máximo) al final
Reajustar el montículo O(log n)
Inestable | In situ O(1) | Óptimo en espacio
Comparación completa de algoritmos de ordenación
| Algoritmo | Mejor | Promedio | Peor | Espacio | Estabilidad |
|---|---|---|---|---|---|
| Ordenación de burbuja | O(n) | O(n²) | O(n²) | O(1) | Estable |
| Ordenación por selección | O(n²) | O(n²) | O(n²) | O(1) | Inestable |
| Ordenación por inserción | O(n) | O(n²) | O(n²) | O(1) | Estable |
| Ordenación rápida | O(n log n) | O(n log n) | O(n²) | O(log n) | Inestable |
| Ordenación por fusión | O(n log n) | O(n log n) | O(n log n) | O(n) | Estable |
| Ordenación por montículos | O(n log n) | O(n log n) | O(n log n) | O(1) | Inestable |
| Ordenación de Shell | O(n log n) | O(n^1.3) | O(n²) | O(1) | Inestable |
Otras extensionesRecomendaciones prácticas: para escenarios generales, priorice la ordenación rápida; si necesita estabilidad, elija la ordenación por fusión; si la memoria es extremadamente limitada, elija la ordenación por montículos; para datos a pequeña escala o casi ordenados, elija la ordenación por inserción.