Algoritmos de ordenación paso a paso
Mira cómo ordenan burbuja, selección, inserción, mergesort y quicksort: cada comparación e intercambio, con la línea del código Java que se está ejecutando. Avanza paso a paso, vuelve atrás y compara cuántas operaciones hace cada uno con el mismo array.
Burbuja
Paso 1 de 87Comparaciones: 0Intercambios: 0[29, 10, 14, 37, 13, 5, 22, 31, 8, 18]
Array inicial: [29, 10, 14, 37, 13, 5, 22, 31, 8, 18].
- se comparan
- se mueve
- en su sitio
Código Java
1static void burbuja(int[] a) {2 for (int i = 0; i < a.length - 1; i++) {3 boolean cambio = false;4 for (int j = 0; j < a.length - 1 - i; j++) {5 if (a[j] > a[j + 1]) {6 int t = a[j]; a[j] = a[j + 1]; a[j + 1] = t;7 cambio = true;8 }9 }10 if (!cambio) break;11 }12}
Compara cada pareja de vecinos y los intercambia si están al revés: en cada pasada el mayor que queda «sube» al final. Si en una pasada no hay ningún intercambio, ya está ordenado.
Los cinco con este array
Prueba con un array al revés, casi ordenado o con repetidos y mira cómo cambian las cuentas.
| Algoritmo | Comparaciones | Movimientos | Mejor caso | Caso medio | Peor caso | Estable | Sin memoria extra |
|---|---|---|---|---|---|---|---|
| Burbuja | 44 | 24 intercambios | O(n) | O(n²) | O(n²) | Sí | Sí |
| Selección | 45 | 9 intercambios | O(n²) | O(n²) | O(n²) | No | Sí |
| Inserción | 31 | 33 escrituras | O(n) | O(n²) | O(n²) | Sí | Sí |
| Mergesort | 25 | 34 escrituras | O(n log n) | O(n log n) | O(n log n) | Sí | No (array auxiliar) |
| Quicksort | 21 | 18 intercambios | O(n log n) | O(n log n) | O(n²) | No | Sí |
Estable: dos elementos iguales conservan su orden relativo. En Java, Arrays.sort usa un quicksort de doble pivote para los tipos primitivos y un mergesort adaptado (TimSort) para los objetos, que sí es estable.
Los arrays y Arrays.sort se explican en Arrays (Programación). Para practicar trazas como las de los exámenes, tienes los ejercicios de trazas de ordenación sin fin.