Insertando orden: ordenamiento inserción

Hace tiempo había escrito de la manera en que se pueden ordenar datos usando el algoritmo conocido como burbuja (puedes ver ese artículo aquí).  Aunque ese algoritmo es el más fácil de entender, también es el meno eficiente.  ¿Por qué digo que es ineficiente?  Es que la eficiencia de un algoritmo de ordenamiento se mide en base al número de comparaciones (o sea, ifs) y el número de asignaciones que tiene que hacer: entre más hace, más se tarda.

Realmente no hay un algoritmo de ordenamiento que sea ideal para todo tipo de arreglos porque unos funcionan mejor para arreglos que están totalmente desordenados (como lo es el QuickSort) o arreglos que están a medio ordenar.  El algoritmo que voy a cubrir aquí es fácil de entender y de implementar.  Además es muy eficiente para ordenar listas que casi están ordenadas.  El algoritmo es el de ordenamiento por inserción.

Para explicar como funciona, tengo varias imágenes que indican el proceso.  Supongamos que tenemos un arreglo de 10 elementos desordenados como el que se ve aquí:


Lo que vamos a hacer es comparar el segundo elemento con el primero.  Si es menor, los intercambio y si no, lo dejo como está y avanzo al siguiente elemento.  En este caso 10 es mayor a 3 así que no hago nada.  Esto se puede ver en esta figura:


Ahora va el tercer elemento.  Lo comparo con el segundo y veo que es menor asi que los intercambio.  Luego lo comparo con el primero y también es menor así que los intercambio.  Como ya es el primer elemento, ahi le paro (es el menor de todos los que he revisado hasta ahorita).  Este proceso lo pueden ver en estas figuras:


Ahora vamos con el cuarto elemento (el 8) y lo comparo con el tercero (10).  Como es menor los intercambio y lo comparo con el segundo (3).  Como no es menor, ahi se queda.  Estas son las imágenes:

Ahora hago lo mismo con el quinto elemento (15) el cual no se mueve por ser mayor que el cuarto (10) como se ve aquí:


Lo mismo con el sexto (5):


Ahora con el séptimo:


Y ahora el octavo:


Ahora el noveno.  Fíjate que como el 5 está repetido en la posición 3, no lo sustituye y se queda en la posición 4 como se ve en estas imágenes:


Y ahora con el último elemento:


Y al final queda el arreglo listo:

Para otra explicación, encontré este video que lo explica bastante bien.  Este es:

Dije que era de fácil implementación, así que vamos a ver como funciona.  Este sería el código en C:


Después de verlo, decidí que se podía optimizar reduciendo el número de asignaciones y quedó así:


Cuando lo ejecutas, se ve así:


Bien, ahora veamos en Visual Basic 6.  Al correrlo, se vería así:


El código sería este.  Fíjate que en el ciclo while tuve que poner un If para comparar el valor del arreglo porque me marcaba error al comparar el elemento del arreglo si j era menor a 0.  Sé que son más comparaciones y disminuye la velocidad de ordenamiento (aunque si lo corres en un CoreDuo o el Quad no notas la diferencia).


Al igual que con el ejemplo de ordenamiento burbuja, implementar el algoritmo en VB 2005 es más engorroso porque no se pueden hacer arreglos de controles (en el ejemplo de VB6, todas las cajas de texto eran un arreglo llamado txtNum), así que hice una subrutina que copia lo que hay en las cajas de texto al arreglo y otro que pasa lo que tiene el arreglo a las cajas de texto.  Fuera de eso, es casi idéntico al código de VB6.  Así se ve cuando se ejecuta:


Y este es el código:


Espero que todo haya quedado claro.  Si te quedaron dudas, déjame un comentario.

¡Saludos!