¿Cómo ordenar un arreglo por selección?


Este escrito explica como hacer un ordenamiento de una arreglo por el método de selección. Primero explica la idea general en español, para después explicarla gráficamente y finalmente se escribe el algoritmo en el lenguaje Java.

La idea general para ordenar un arreglo por el método  selección es la siguiente:

  • El arreglo se divide en dos partes: la parte ordenada y la que está sin ordenar.
  • Se busca el menor elemento en la parte no ordenada.
  • Ese elemento se intercambia por el primero de la parte no ordenada.
  • Ese elemento ya pertenece a la parte ordenada.

Claro, así explicado no se entiende mucho, lo mejor es que lo veamos en forma gráfica.

Ordenamiento por Selección

Ordenamiento por Selección: El gráfico

Como siempre, sino alcanzas a ver el gráfico haz clic en él para verlo más grande. Comenzamos con un arreglo que está desordenado, el primero, el que está todo en gris. Ese color significa, el gris, que todo el arreglo está desordenado, a medida que se va ordenando va quedando en rojo.

Lo primero es buscar el menor elemento del arreglo. En el gráfico en el número 11 que está marcado con un círculo azul, y lo intercambiamos por el primer elemento, en este caso el 48. Este intercambio lo dibujé con una línea con flechas. Ahora el 11 queda al principio y el 48 donde estaba el 11. Ahora el 11 está ordenado  (en la gráfica esto se simboliza con color rojo).

En este punto volvemos a repetir, pero esta vez buscamos el menor de la parte no ordenada (la parte gris). En este caso es el 14 y lo intercambiamos con el 45 que es el primero de la parte no ordenada. Ahora tenemos el 11 y el 14 ordenados, por lo que en la gráfica quedan marcados en rojo.

Volvemos a repetir lo anterior, buscamos el menor, 44, y los intercambiamos con el 45, el primero de la parte no ordenada. Después el 47 con el 71 y así sucesivamente hasta que todo el arreglo queda ordenado. Sugiero que sigas el gráfico paso a paso en este momento para entenderlo.

Si ya entiendes la anterior y sabes java, ya estás listo para enfrentarte al algoritmo escrito en ese lenguaje:

Algoritmo de ordenamiento por selección

Algoritmo en java de un ordenamiento por selección

Comienza con ciclo for que recorre el arreglo desde el principio hasta el penúltimo elemento. Esto es por que si todos los demás están ordenados pues el último ya está ordenado. La variable de este ciclo, la i,  es la que indica que es lo que va quedando ordenado.

Primero supone que el elemento menor es el primero del ciclo y que está en la posición cual. Ahora viene el segundo ciclo que recorre la parte no ordenada del arreglo buscando el menor. Si encuentra un número menor al que está en la variable menor lo cambia, al igual que su posición cual.

Después de terminar el ciclo pues sencillamente intercambia el elemento en la primera posición no ordenada por el que acabamos de encontrar, el menor. Para ello usa una variable temp.

En este punto te aconsejo que hagas una prueba de escritorio del código en Java e intentes ver como funciona. Las pruebas de escritorio son una excelente herramienta para desarrollar las habilidades que necesitas para entender algoritmos.

Y si ahora lo dominas intenta simplificarlo, por ejemplo se puede prescindir de la variable menor y usar solo cual.

Y eso es todo. Espero en un futuro próximo estar escribiendo otro artículo sobre otro método de ordenamiento. Hasta entonces. Pero no olvides que he escrito otros artículos sobre Estructuras de Datos:

 

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s

A %d blogueros les gusta esto: