En el post anterior hablamos sobre el https://devs4j.com/2018/12/19/algoritmo-de-la-burbuja-en-java-bubble-sort/ en este post veremos otro algoritmo de ordenamiento llamado por selección o (Selection sort).
De igual modo que con el método de la burbuja, el algoritmo de selección dividirá el arreglo en 2 particiones, una ordenada y una desordenada, durante la ejecución la partición ordenada irá creciendo y la desordenada irá disminuyendo.
Algoritmo
El algoritmo seguirá los siguientes pasos:
- Se definirá un indice de partición (partitionIndex) en la última posición del arreglo
- Se definirá un indice (i) para recorrer el arreglo
- Se definirá una variable (maxValue) como el elemento mayor apuntando inicialmente al primer elemento
- Se buscará el elemento mayor entre los elementos que se encuentren antes del partitionIndex se utilizará la variable maxValue para determinarlo.
- El elemento mayor se intercambiará con el elemento en la posición partitionIndex.
- Se reducirá en uno el partitionIndex.
- Se reiniciará el valor del indice i a 0
- El proceso anterior se repetirá hasta que el arreglo completo se ordene
Veamos el código
Una vez que entendimos el algoritmo veamos el código:
public class SelectionSort {
public void sortArray(int[] array) {
for (int i = array.length - 1; i > 0; i--) {
int maxValue = 0;
for (int j = 0; j < i; j++) {
if (array[j + 1] > array[maxValue]) {
maxValue = j + 1;
}
}
swap(array, i, maxValue);
printArray(array);
}
}
public void printArray(int[] array) {
for (int i = 0; i < array.length; i++) {
System.out.printf("%d \t", array[i]);
}
System.out.println();
}
public void swap(int[] array, int a, int b) {
int value = array[b];
array[b] = array[a];
array[a] = value;
}
public static void main(String[] args) {
SelectionSort selectionSort = new SelectionSort();
int[] array = { 10, 1, 5, 40, 12, 34, 44, 12, 11, 9 };
selectionSort.printArray(array);
selectionSort.sortArray(array);
selectionSort.printArray(array);
}
}Ejecutando el algoritmo y analizando los resultados
10 1 5 40 12 34 44 12 11 9
10 1 5 40 12 34 9 12 11 44
10 1 5 11 12 34 9 12 40 44
10 1 5 11 12 12 9 34 40 44
10 1 5 11 9 12 12 34 40 44
10 1 5 11 9 12 12 34 40 44
10 1 5 9 11 12 12 34 40 44
9 1 5 10 11 12 12 34 40 44
5 1 9 10 11 12 12 34 40 44
1 5 9 10 11 12 12 34 40 44
1 5 9 10 11 12 12 34 40 44 En la salida anterior podemos analizar el siguiente comportamiento:
- Los elementos mayores se van colocando del lado derecho
- El arreglo se va ordenando de derecha a izquierda
- El partitionIndex se va moviendo hacia la izquierda
- Se requiere un número menor de intercambios que en el algoritmo de la burbuja
Características del algoritmo
- No requiere arreglos adicionales para el ordenamiento
- La complejidad es de O(n²)
- Requiere menos cambios que el algoritmo de la burbuja (Bubble sort) para ordenar el arreglo
- Es un algoritmo inestable (Si existe un elemento duplicado cambiarán de posición)
- Es más eficiente que el algoritmo de la burbuja (Bubble sort)
Para estar al pendiente sobre nuestro contenido nuevo síguenos en nuestras redes sociales https://www.facebook.com/devs4j/ y https://twitter.com/devs4j.
Si hay algún algoritmo que te gustaría que desarrollemos coméntenlo en nuestras redes sociales o en la sección de comentarios del post.
Autor: Alejandro Agapito Bautista
Twitter: @raidentrance
Contacto:raidentrance@gmail.com
devs4j 