Selección Ordenar en Java Programa con ejemplo
james hartman
⚡ Resumen inteligente
Ordenación por selección en Java Escanea repetidamente la parte no ordenada de una matriz, encuentra el valor restante más pequeño y lo intercambia en su posición, completando el trabajo con un máximo de n-1 intercambios, independientemente del orden de entrada.
¿Cómo funciona la clasificación por selección?
Selection Sort implementa un algoritmo de clasificación simple de la siguiente manera:
- El algoritmo busca repetidamente el elemento más bajo.
- Intercambiar el elemento actual con un elemento que tenga el valor más bajo
- Con cada iteración/paso de clasificación de selección, los elementos se intercambian.
Por lo tanto, cada pase trata el matriz como dos regiones: un bloque ordenado que crece desde la izquierda y un bloque desordenado que se reduce hacia la derecha. El algoritmo recorre el bloque desordenado, recuerda el índice del valor más pequeño que encuentra e intercambia ese valor con la primera posición del bloque desordenado.
Debido a que solo se produce un intercambio por pasada, un array de n elementos se ordena después de como máximo n-1 intercambios. Esa propiedad es lo que diferencia esta rutina de las demás rutinas para principiantes. Java algoritmos de ordenación, que mueven los datos con mucha más frecuencia.
El tracA continuación se muestra el array de ejemplo {860, 8, 200, 9} exactamente como lo imprime el programa en la siguiente sección durante su ejecución.
| Pasó | Comparaciones impresas | Valor más pequeño encontrado | Matriz después del intercambio |
|---|---|---|---|
| Comenzar | - | - | 860 8 200 9 |
| 1 | 860 y 8, 8 y 200, 8 y 9 | 8 | 8 860 200 9 |
| 2 | 860 y 200, 200 y 9 | 9 | 8 9 200 860 |
| 3 | 200 y 860 | 200 | 8 9 200 860 |
Dos detalles en ese tracVale la pena detenerse en estos puntos. Primero, la pasada 3 sigue reportando un intercambio aunque el orden no cambie, porque el valor restante más pequeño ya se encuentra en el índice actual y el programa intercambia el elemento consigo mismo. Segundo, el número de comparaciones disminuye en uno en cada pasada (tres, luego dos, luego uno), que es el patrón que explica las cifras de complejidad que aparecen más abajo en la página.
Java Programa para implementar la clasificación por selección
La clase que se muestra a continuación se llama SelectionSortAlgo y pertenece al paquete com.guru99. El método main() declara el array de ejemplo, lo imprime, lo pasa a selection() para su ordenación y lo vuelve a imprimir. La función auxiliar printArray() escribe todos los elementos en una sola línea, lo que genera el registro legible de paso a paso.
Dentro de selection(), el bucle exterior marca el límite entre las regiones ordenadas y no ordenadas, la variable index almacena la posición del valor más pequeño visto hasta el momento, y las tres asignaciones al final de cada pasada realizan el intercambio.
package com.guru99; public class SelectionSortAlgo { public static void main(String a[]) { int[] myArray = {860,8,200,9}; System.out.println("------Before Selection Sort-----"); printArray(myArray); selection(myArray);//sorting array using selection sort System.out.println("-----After Selection Sort-----"); printArray(myArray); } public static void selection(int[] array) { for (int i = 0; i < array.length - 1; i++) { System.out.println("Sort Pass Number "+(i+1)); int index = i; for (int j = i + 1; j < array.length; j++) { System.out.println("Comparing "+ array[index] + " and " + array[j]); if (array[j] < array[index]){ System.out.println(array[index] + " is greater than " + array[j] ); index = j; } } int smallerNumber = array[index]; array[index] = array[i]; array[i] = smallerNumber; System.out.println("Swapping Elements: New Array After Swap"); printArray(array); } } static void printArray(int[] array){ for(int i=0; i < array.length; i++) { System.out.print(array[i] + " "); } System.out.println(); } }
Salida:
Al compilar y ejecutar la clase, se genera el siguiente registro en la consola, con un bloque de salida por cada pasada.
------Before Selection Sort----- 860 8 200 9 Sort Pass Number 1 Comparing 860 and 8 860 is greater than 8 Comparing 8 and 200 Comparing 8 and 9 Swapping Elements: New Array After Swap 8 860 200 9 Sort Pass Number 2 Comparing 860 and 200 860 is greater than 200 Comparing 200 and 9 200 is greater than 9 Swapping Elements: New Array After Swap 8 9 200 860 Sort Pass Number 3 Comparing 200 and 860 Swapping Elements: New Array After Swap 8 9 200 860 -----After Selection Sort----- 8 9 200 860
Dos problemas sorprenden a los principiantes cuando ejecutan este ejemplo por primera vez. Debido a que el archivo declara package com.guru99;, la fuente debe vivir en un lugar coincidente com/guru99 directorio, de lo contrario el compilador informa una discrepancia en el nombre del paquete o de la clase. La clase debe entonces iniciarse por su nombre completo, java com.guru99.SelectionSortAlgo, porque simple java SelectionSortAlgo genera NoClassDefFoundError.
Los límites del bucle son otra trampa común. El bucle exterior se detiene en array.length - 1 y el bucle interior comienza en i + 1; cambiar cualquiera de los límites produce un paso vacío adicional o una ArrayIndexOutOfBoundsException.
Complejidad temporal y espacial del algoritmo de ordenación por selección.
El bucle interno del programa siempre se ejecuta hasta el final del array, por lo que el algoritmo realiza el mismo número de comparaciones independientemente del aspecto de los datos. Para un array de n elementos, ese total es n(n-1)/2, que para la muestra de cuatro elementos es igual a seis, y la salida anterior imprime exactamente seis líneas de comparación.
| Caso | Comparaciones | permutas | Complejidad de tiempo | Espacio auxiliar |
|---|---|---|---|---|
| Mejores (matriz ya ordenada) | n(n-1)/2 | n-1 | O (n²) | O (1) |
| Promedio (orden aleatorio) | n(n-1)/2 | n-1 | O (n²) | O (1) |
| Peor (ordenado en orden inverso) | n(n-1)/2 | n-1 | O (n²) | O (1) |
De esa fila uniforme de cifras se derivan tres consecuencias:
- La ordenación por selección no es adaptativa. La entrada ordenada cuesta exactamente lo mismo que la entrada invertida, por lo que no hay ningún atajo de salida anticipada del tipo ordenamiento de burbuja ofrece.
- El número de intercambios es el punto fuerte del algoritmo. Como máximo, se producen n-1 intercambios, lo que es mucho menor que el número cuadrático de movimientos que pueden realizar otros algoritmos de ordenación simples.
- El uso de memoria es constante. Solo se necesitan los contadores del bucle y las dos variables temporales index y smallerNumber, por lo que el espacio auxiliar es O(1) y la ordenación se realiza in situ.
El crecimiento cuadrático es el límite práctico. Duplicar el tamaño del arreglo prácticamente cuadruplica el trabajo de comparación, por lo que la ordenación por selección es más adecuada para la enseñanza, arreglos pequeños y código embebido que para conjuntos de datos de producción, donde los algoritmos O(n log n) son la opción correcta.
Ventajas y desventajas del algoritmo de ordenación por selección.
Comprender dónde ayuda el algoritmo y dónde perjudica facilita la decisión de cuándo es razonable recurrir a él.
Ventajas
- La lógica es corta y legible, por lo que es un ejercicio estándar de primera clasificación junto con tipo de inserción.
- La ordenación se realiza in situ, por lo que no se asigna una segunda matriz y el uso de memoria no aumenta con la entrada.
- Realiza como máximo n-1 escrituras en la matriz, lo cual es importante en sistemas de almacenamiento donde las escrituras son lentas o desgastan el medio.
- Su tiempo de ejecución es completamente predecible, ya que el número de comparaciones depende únicamente de la longitud del array.
Desventajas
- Cada caso es O(n²), por lo que el algoritmo no es escalable a colecciones grandes.
- No puede detectar una matriz ya ordenada y, por lo tanto, nunca termina antes de tiempo.
- La forma clásica que se muestra arriba es inestable, por lo que dos valores iguales pueden terminar en orden inverso.
- Realiza comparaciones con mayor frecuencia que la ordenación por inserción en datos casi ordenados, donde la ordenación por inserción se aproxima a un tiempo lineal.
En resumen, elija el algoritmo de ordenación por selección cuando el array sea pequeño y cada escritura sea costosa, y evítelo siempre que el conjunto de datos sea grande o ya esté casi ordenado.
Ordenación por selección vs. BubblOrdenación e frente a ordenación por inserción
Los tres algoritmos son algoritmos de ordenación por comparación cuadrática in situ, pero se comportan de manera diferente cuando cambia la forma de la entrada.
| Criterio | Tipo de selección | Bubbly ordenar | Tipo de inserción |
|---|---|---|---|
| Mejores-case tiempo | O (n²) | O (n) | O (n) |
| Tiempo promedio y en el peor de los casos | O (n²) | O (n²) | O (n²) |
| Intercambios o cambios en el peor de los casos. | Intercambios n-1 | n(n-1)/2 intercambios | Hasta n(n-1)/2 turnos |
| Estable | No | Sí: | Sí: |
| Adaptable a entradas ordenadas | No | Sí: | Sí: |
| Espacio auxiliar | O (1) | O (1) | O (1) |
| Uso típico | Se requiere la menor cantidad de escrituras. | Enseñanza y detección de datos clasificados | Matrices pequeñas o casi ordenadas |
La tabla explica una respuesta común en las entrevistas de trabajo. El algoritmo de ordenación por selección es superior en cuanto al número de intercambios, el de burbuja destaca por reconocer entradas ya ordenadas, y el de inserción suele ser el más rápido de los tres en la práctica, ya que los datos reales a menudo están parcialmente ordenados. Ninguno de ellos compite con el de ordenación por fusión ni con el de ordenación rápida una vez que el array supera unas pocas docenas de elementos.
