viernes, 19 de febrero de 2016

Método de ordenamiento por selección usando Java

Es un método poco eficiente pero fácil de entender, en caso de ordenar números éste consistirá en determinar cual es el menor de todos y ubicarlo en la primera posición, luego determinar cual es el segundo menor y ubicarlo en la segunda posición hasta terminar con todo los numero.

La cantidad de comparaciones para éste método de ordenamiento está dada por la fórmula: c(n) = (n² – n)/2; es decir para un arreglo de 10 elementos el numero de comparaciones es de (10² – 10)/2 = 45; en el siguiente código fuente al descomentariar la linea 7 y compilar notarán el número de comparaciones.

Analizando podemos darnos cuenta que aunque nuestro arreglo a mitad del proceso este ordenado, el método seguirá haciendo comparaciones innecesarios haciéndolo poco eficiente sobre todo para grandes cantidades de elementos.

Sin más preámbulos, el código:




class seleccion{
 public static void ordenar(int[] arreglo){
  int contador = 1;//solo util para contar las comparaciones
  for (int i = 0; i < arreglo.length - 1; i++){
   int min = i;
   for (int j = i + 1; j < arreglo.length; j++){
   //System.out.println("Comparacion #" + contador);
    contador++;
    if (arreglo[j] < arreglo[min]){
     min = j;
    }
   }
   if (i != min){
    int aux= arreglo[i];
    arreglo[i] = arreglo[min];
    arreglo[min] = aux;
   }
  }
 }
 public static void imprimirLista(int[] arreglo){
  for(int i = 0; i < arreglo.length;i++){
   System.out.print(arreglo[i]+",");
  }
  System.out.println();
 }
 public static void main(String[] args){
  int lista[] = {9,1,4,2,8,3,5,6,7,0};
  System.out.print("Lista desordenada: ");
  imprimirLista(lista);
  
  ordenar(lista);

  System.out.print("Lista ordenada: ");
  imprimirLista(lista);
 }
}

Deseaba en ésta entrada hacer una prueba de escritorio al método, pero haré algo mejor, agregaré comentarios de salida al codigo para detallar cada comparación de la lista que ustedes introduzcan, abajo está el link de descarga, espero les guste y hagan sus comentarios.

Descarga aqui codigo con prueba de escritorio



Entrada destacada

Matriz de adyacencia para un grafo

"La matriz de adyacencia es una matriz cuadrada que se utiliza como una forma de representar relaciones binarias."; aunque pa...