Ordenar como un humano
Los algoritmos de inserción ordenan como lo hacemos nosotros. Supongamos que tenemos una serie de papeles con un número cada uno ya ordenados, si los tenemos en la mano para insertar uno buscamos su lugar y lo ponemos sin mas. Si en lugar de uno sobre otros los tenemos dispuestos de forma consecutiva en una mesa, buscamos su lugar, desplazamos todos los elementos mayores para dejarle hueco, y lo ubicamos.Esto es lo que hace nuestro algoritmo, para un elemento dado, se lo guarda en un temporal, recorre la lista en sentido inverso desde el anterior a su posición hacia el comienzo, si el valor es mayor lo mueve una posición a la derecha y repite el proceso hasta que el elemento sea menor o igual, en ese momento deja de mover y posiciona el elemento en el temporal en su lugar correcto.
ALGORITMO Insercion (arreglo,sentido,primero,ultimo)
BUCLE pivote DESDE primero+1 HASTA ultimo
temp ← arreglo(pivote)
pos ← pivote
REPETIR
SI (pos-1 < primero) O BIEN (COMPARA(temp,arreglo(pos-1),sentido) = 1) ENTONCES
SALIR_DE_REPETIR
FIN SI
arreglo(pos) ← arreglo(pos-1)
pos ← pos-1
FIN REPETIR
arreglo(pos) ← temp
FIN BUCLE
Empleo un procedimiento para mover un valor sobre otro, esto me permite diseñar un algoritmo que funciona con cualquier tipo de elementos, no solo un arreglo de enteros, y que este me cuente los movimientos necesarios, igualando la velocidad de las llamadas con el resto de algoritmos. El resultado es el siguiente:
01 DEFine PROCedure Insercion (arreglo,sentido,primero,ultimo) 02 LOCal repetir,pivote,pos,temp 03 : 04 IF ultimo = 0 THEN ultimo=DIMN(arreglo) 05 : 06 FOR pivote = 1 TO ultimo 07 temp = arreglo(pivote) 08 pos = pivote 09 REPeat repetir 10 IF pos-1 < primero THEN EXIT repetir 11 IF COMPARA(temp,arreglo(pos-1),sentido) = 1 THEN 12 EXIT repetir 13 END IF 14 : 15 MUEVE arreglo(pos-1),arreglo(pos) 16 pos=pos-1 17 END REPeat repetir 18 MUEVE temp,arreglo(pos) 19 END FOR pivote 20 END DEFine
Este algoritmo consigue dos mejoras importantes sobre la burbuja, la primera es que mover un elemento requiere un solo paso en lugar de los tres que requiere un intercambio, por lo que el número de movimientos de elementos se reduce, por otro usa el sistema de dividir la lista en sublistas y posicionar los elementos en su lugar, esto es similar a lo que hace el Quicksort, aunque la rutina de intercambio mueve muchas veces los mismos valores mientras que Quicksort minimiza los movimientos. Como este algoritmo es muy muy sencillo, requiere solo una posición auxiliar para guardar un dato, y es bastante mas eficiente que la burbuja, por lo que es el preferido cuando no existe la posibilidad de usar la recursión. También se usa mucho combinado con Quicksort cuando las sublistas tienen ya pocos elementos, momento en que deja de ser eficiente, depende mucho de la máquina, podemos hablar de unos 100 en máquinas rápidas, y como mínimo entre 10 y 20 elementos en máquinas mas lentas.
La variante del señor Shell
He visto mencionar el nombre de este algoritmo queriendo traducir el nombre de su creador, Donald Shell, lo que no es correcto (sería Ordenación de concha o de caparazón). Esta variante es similar a la ordenación por Peine, en lugar de mover elementos separados por una posición lo hace entre elementos separados varias posiciones, pero con la gran ventaja de que va creando sublistas de forma similar a las de Quicksort ya que todos los elementos de la sublista serán mayores que los ubicados a su izquierda y menores que los de su derecha. Reducimos el tamaño de las sublistas en cada paso, hasta que se convierta en 1 y pasa a ser un algoritmo por inserción normal. Como siempre elegir el tamaño de cada sublista es importante para la eficiencia del algoritmo:- La propuesta original de Shell es usar f(n+1)=ENTERO(n/2), para una lista de 100 elementos sería 50,25,12,6,3,1 sencillo y directo. Lo mas usado realmente es f(n+1)=ENTERO(n/2.2), con esta pequeña diferencia se ahorran particiones sin mermar la eficiencia, o lo que es lo mismo se emplea f(n+1)=ENTERO(n*5/11) cuando el lenguaje trata mal con decimales
- La propuesta de Hibbard es de usar f(n)=2n − 1, resultando f(1)=1,f(2)=3,f(3)= 7,f(4)=15,f(5)=31,f(6)=63,f(7)=127. Para una lista de 100 elementos sería calcular la secuencia hasta que sea mayor de 100 e ir usando los elementos, lo que resultaría 63,31,15,7,3,1
- La propuesta de Sedgewick es la que mejor resultado obtiene pero no es
de cálculo muy directo, hay que usar el resultado de ir alternando los valores producidos
por dos funciones:
- f(n) = 9(4n) − 9(2n) + 1 ⇨ f(0)=1,f(1)=19,f(2)=109,f(3)=505,...
- g(n) = (2n+2) * (2n+2-3) + 1 ⇨ g(0)=5,g(1)=41,g(2)=209,g(3)=929,...
- La secuencia completa sería 1,5,19,41,109,209,505,929... y para 100 elementos usar 41,19,5,1
ALGORITMO Shell (arreglo,sentido,primero,ultimo)
inc ← ultimo - primero
REPETIR
inc ← INT(inc/2.2)
SI inc <= 2 ENTONCES
inc=1
FIN_SI
BUCLE pivote DESDE inc HASTA ultimo
temp ← arreglo(pivote)
pos ← pivote
REPETIR
SI (pos-inc < primero) O BIEN (COMPARA(temp,arreglo(pos-inc),sentido) = 1) ENTONCES
SALIR_DE_REPETIR
FIN SI
arreglo(pos) ← arreglo(pos-inc)
pos ← pos-inc
FIN REPETIR
arreglo(pos) ← temp
FIN BUCLE
HASTA QUE inc=1
Y en nuestro SuperBASIC lo traduzco así, solo se añade un bucle externo al algoritmo básico de inserción.
01 DEFine PROCedure Shell (arreglo,sentido,primero,ultimo) 02 LOCal bucle1,repetir,inc,pivote,pos,temp 03 : 04 IF ultimo = 0 THEN ultimo=DIMN(arreglo) 05 : 06 inc = ultimo - primero 07 REPeat bucle1 08 inc=INT(inc/2.2) 09 IF inc <= 2 THEN inc=1 10 : 11 FOR pivote = inc TO ultimo 12 temp = arreglo(pivote) 13 pos = pivote 14 REPeat repetir 15 IF pos-inc < primero THEN EXIT repetir 16 IF COMPARA(temp,arreglo(pos-inc),sentido) = 1 THEN 17 EXIT repetir 18 END IF 19 : 20 MUEVE arreglo(pos-inc),arreglo(pos) 21 pos=pos-inc 22 END REPeat repetir 23 MUEVE temp,arreglo(pos) 24 END FOR pivote 25 IF inc = 1 THEN EXIT bucle1 26 END REPeat bucle1 27 END DEFine
No hay comentarios:
Publicar un comentario