Algorithms in Java: sorting and searching
Bubble, selection, insertion and binary search, with an animated visualiser showing every comparison and every swap.
En el día a día usarás Arrays.sort() y Collections.sort() (muy optimizados).
Pero entender cómo ordena y busca un ordenador te enseña a pensar en coste: no es lo
mismo O(n²) que O(log n).
Sorting visualiser
Elige un algoritmo y pulsa «Ordenar». Cada barra es un número; las que se comparan se resaltan.
Laboratorio: ordenar un array interactivo
…
Burbuja en Java
for (int i = 0; i < n - 1; i++)
for (int j = 0; j < n - 1 - i; j++)
if (a[j] > a[j + 1]) {
int tmp = a[j]; a[j] = a[j + 1]; a[j + 1] = tmp;
}Binary search
Sobre un array ya ordenado: mira el elemento del medio; si es mayor que el buscado, descarta la mitad derecha; si es menor, la izquierda. Repite. En un millón de elementos, ~20 pasos.
Laboratorio: búsqueda binaria paso a paso interactivo
…
En Java ya lo tienes hecho:
Arrays.binarySearch(array, valor)
(el array debe estar ordenado).Complexity (Big-O)
| Algoritmo | Mejor | Medio | Peor |
|---|---|---|---|
| Burbuja / Selección / Inserción | O(n)* | O(n²) | O(n²) |
Merge sort / Arrays.sort (objetos) | O(n log n) | O(n log n) | O(n log n) |
Quicksort / Arrays.sort (primitivos) | O(n log n) | O(n log n) | O(n²) |
| Búsqueda lineal | O(1) | O(n) | O(n) |
| Búsqueda binaria | O(1) | O(log n) | O(log n) |
* la inserción es O(n) si el array ya está casi ordenado.
Check what you've learned
¿Qué requisito tiene la búsqueda binaria?
El bubble sort es O(n²). Si tardas 1 s con 1000 elementos, con 2000 tardarás ~…
¿Cuántos pasos, más o menos, necesita la búsqueda binaria en 1 000 000 de elementos?