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