martes, 22 de noviembre de 2016

Programación del Sinclair QL (XIII): Ordenación por inserción, el mejor iterativo



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
El algoritmo general es el siguiente:

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