1. Introducción
En este tutorial, aprenderemos la clasificación por selección , veremos su implementación en Java y analizaremos su rendimiento.
2. Descripción general del algoritmo
La clasificación por selección comienza con el elemento en la primera posición de una matriz sin clasificar y explora los elementos posteriores para encontrar el elemento más pequeño . Una vez encontrado, el elemento más pequeño se intercambia con el elemento en la primera posición.
El algoritmo luego pasa al elemento en la segunda posición y escanea a través de los elementos subsiguientes para encontrar el índice del segundo elemento más pequeño. Una vez encontrado, el segundo elemento más pequeño se intercambia con el elemento en la segunda posición.
Este proceso continúa hasta que llegamos al n-1º elemento de la matriz, que coloca al n-1º elemento más pequeño en la n-1º posición. El último elemento cae automáticamente en su lugar, en la n-1ª iteración, ordenando así la matriz.
Encontramos el elemento más grande en lugar del elemento más pequeño para ordenar la matriz en orden descendente.
Veamos un ejemplo de una matriz sin clasificar y ordénela en orden ascendente para comprender visualmente el algoritmo.
2.1. Un ejemplo
Considere la siguiente matriz sin clasificar:
int [] arr = {5, 4, 1, 6, 2}
Iteración 1
Teniendo en cuenta el funcionamiento anterior del algoritmo, comenzamos con el elemento en la 1ª posición - 5 - y escaneamos todos los elementos posteriores para encontrar el elemento más pequeño - 1. Luego intercambiamos el elemento más pequeño con el elemento en la 1ª posición.
La matriz modificada ahora se ve así:
{1, 4, 5, 6, 2}
Total de comparaciones realizadas: 4
Iteración 2
En la segunda iteración, pasamos al segundo elemento - 4 - y exploramos los elementos subsiguientes para encontrar el segundo elemento más pequeño - 2. Luego intercambiamos el segundo elemento más pequeño con el elemento en la segunda posición.
La matriz modificada ahora se ve así:
{1, 2, 5, 6, 4}
Total de comparaciones realizadas: 3
Continuando de manera similar, tenemos las siguientes iteraciones:
Iteración 3
{1, 2, 4, 6, 5}
Total de comparaciones realizadas: 2
Iteración 4
{1, 2, 4, 5, 6}
Total de comparaciones realizadas: 1
3. Implementación
Implementemos el ordenamiento por selección usando un par de bucles for :
public static void sortAscending(final int[] arr) { for (int i = 0; i < arr.length - 1; i++) { int minElementIndex = i; for (int j = i + 1; j arr[j]) { minElementIndex = j; } } if (minElementIndex != i) { int temp = arr[i]; arr[i] = arr[minElementIndex]; arr[minElementIndex] = temp; } } }Eso sí, para revertirlo podríamos hacer algo bastante similar:
public static void sortDescending(final int[] arr) { for (int i = 0; i < arr.length - 1; i++) { int maxElementIndex = i; for (int j = i + 1; j < arr.length; j++) { if (arr[maxElementIndex] < arr[j]) { maxElementIndex = j; } } if (maxElementIndex != i) { int temp = arr[i]; arr[i] = arr[maxElementIndex]; arr[maxElementIndex] = temp; } } }Y con un poco más de esfuerzo, podríamos combinarlos usando Comparator s.
4. Resumen de desempeño
4.1. Hora
En el ejemplo que vimos anteriormente, seleccionar el elemento más pequeño requería un total de (n-1) comparaciones seguidas de cambiarlo a la primera posición. De manera similar, la selección del siguiente elemento más pequeño requirió comparaciones totales (n-2) seguidas de intercambio en la segunda posición, y así sucesivamente.
Así, partiendo del índice 0, realizamos n-1, n-2, n-3, n-4…. 1 comparaciones. El último elemento cae automáticamente en su lugar debido a iteraciones e intercambios anteriores.
Matemáticamente, la suma de los primeros n-1 números naturales nos dirá cuántas comparaciones necesitamos para ordenar una matriz de tamaño n usando el Orden de selección.
La fórmula para la suma de n números naturales es n (n + 1) / 2 .
En nuestro caso, necesitamos la suma de los primeros n-1 números naturales. Por lo tanto, reemplazamos n con n-1 en la fórmula anterior para obtener:
(n-1) (n-1 + 1) / 2 = (n-1) n / 2 = (n ^ 2-n) / 2
A medida que n ^ 2 crece de manera prominente a medida que crece n , consideramos la mayor potencia de n como el punto de referencia de rendimiento, lo que hace que este algoritmo tenga una complejidad temporal de O (n ^ 2).
4.2. Espacio
En términos de complejidad del espacio auxiliar, la clasificación por selección requiere una variable adicional para mantener el valor temporalmente para el intercambio. Por lo tanto, la complejidad del espacio de Selection Sort es O (1) .
5. Conclusión
Selection Sort es un algoritmo de clasificación muy simple de entender e implementar. Desafortunadamente, su complejidad de tiempo cuadrático la convierte en una técnica de clasificación cara . Además, dado que el algoritmo tiene que escanear a través de cada elemento, el mejor caso, el caso promedio y la complejidad del tiempo del peor caso son los mismos .
Otras técnicas de clasificación como Insertion Sort y Shell Sort también tienen una complejidad de tiempo cuadrática en el peor de los casos, pero funcionan mejor en los mejores y en los casos promedio.
Consulte el código completo para Ordenar por selección en GitHub.