|
A continuación se
muestra una aplicación en javascript en la cual tras introducir una
serie de números, estos son ordenados de menor a mayor. para ello se
puede escoger entre varios algoritmos de ordenación, que efectuaran la
tarea de diferentes maneras.
Se han incluido 5
algoritmos diferentes, que se explican mas abajo. Además en un cuadro
del formulario se nos indica un resumen de todos los pasos que sigue
el algoritmo hasta ordenar todos los números.
Si marcamos las opciones
de mostrar los pasos y mostrar los cambios se nos ira explicando el
proceso paso a paso, mediante alertas con ventanas de aviso.
Para ayudar a la
comparación de los diferentes algoritmos en las casillas del final se
incluyen algunos datos estadísticos: numero de elementos a ordenar,
numero de comparaciones realizadas, numero de movimientos, y tiempo
empleado para realizar la ordenación. Esta ultima opción solo es útil
si desmarcamos las casillas de mostrar los pasos y los movimientos, ya
que si no el tiempo que tardemos en aceptar los avisos influirá en el
tiempo total por lo que no será una medida fiable.
Selección:
Este algoritmo tiene el
siguiente funcionamiento: Comenzando por el primer elemento de la
lista compara este con los demás, y en caso de que otro elemento sea
menor, los intercambia, de manera que el primer elemento pasara ahora
a ser el menor y continuara comparando los restantes con este.
Una vez que termina de comparar con el último, el primer elemento de
la lista será ya el mas pequeño de todos, por lo que procederá a
realizar la misma operación pero comenzando en el segundo elemento de
la lista y sin incluir el primero en las comparaciones. Se repetirá
este proceso hasta llegar al final de la lista.
Este es el algoritmo más lento.
Burbuja:
Este algoritmo consiste
en comparar parejas de elementos, de forma que si el segundo es
menor que el primero los intercambia (el mayor siempre queda el
segundo). Cuando acaba con una pareja continua con la siguiente, que
estará formada por el segundo elemento de la pareja anterior (el
mayor de los dos) y un elemento nuevo. De esta forma cuando acabe de
comparar todas las parejas, el mayor de todos los números quedara al
final de la lista.
Si repite el proceso con todos los elemento menos el que ha quedado el
ultimo (el mayor) quedara el segundo mas grande el antepenúltimo, por
lo que si repetimos este proceso hasta llegar al primero nos quedará
la lista ordenada.
Quiksort:
En este caso escogemos
el primer elemento (pivote) y lo comparamos con los demás, de forma
que si el elemento es mayor no hacemos nada, pero si es menor, lo
intercambiamos por el primer elemento mayor que el pivote que hayamos
encontrado, si repetimos este proceso hasta el final, obtendremos una
lista con la estructura: pivote, menor, menor... mayor, mayor....
Ahora intercambiamos el pivote por el ultimo de los elementos menores
que el mismo, y queda: menor, menor....pivote, mayor, mayor... Si
repetimos el proceso con las dos sublistas de menores y mayores
recursivamente, al final obtendremos la lista ordenada.
Merge:
Este algoritmo es muy
sencillo, divide la lista en dos mitades, y a cada mitad le aplica el
algoritmo recursivamente. Cuando la lista solo contiene dos elementos
los ordena, y ordena esta lista con la su mitad correspondiente.
Repite este proceso recursivamente hasta que ordena las pos mitades
originales y la lista queda ordenada. Para llevar a cabo el proceso,
usa un array temporal, por lo que no se muestran los pasos, pero si se
alerta de ellos si se marca la opción.
Radix:
Este algoritmo trabaja
convirtiendo cada numero binario y tratandolodo como x veces un
digito. De esta forma crea dos arrays, uno con números positivos y
otro con números negativos. Coloca los positivos primero, y en cada
pasada trabaja cada vez con un bit mas (1, 2, 3...). Cuando ya no
hacen falta mas bits para ordenarlo se para. Este es el proceso mas
rápido que hay, pero tiene el inconveniente de que le afecta el tamaño
de los números en su velocidad final, cosa que no sucede en los demás. |