Programación del Sinclair QL (XI): Ordenación por intercambio recursivo, mas sobre el Quicksort

Índice de entradas sobre programación del Sinclair QL

---

Mas consideraciones sobre el Pivote

La elección de un mal pivote es lo que mas ralentiza el algoritmo, en la anterior entrada usé un algoritmo que busca un pivote según recorre los elementos, lo que funciona bien cuando la lista es aleatoria, pero mal cuando esta casi ordenada pues tiende a hacer muchas listas de un solo elemento, lo que al final hace que el algoritmo sea muy ineficiente.

Otra cosa que dije es que el mejor pivote es el valor medio de la lista, lo que es cierto solo si los elementos están distribuidos en la lista de forma regular, si por ejemplo nos encontramos con esta lista [10,3,15,300,9] el valor medio es 67'4, usándolo como pivote obtenemos [10,3,15,9] [300] lo que produce sublistas de un elemento, que es malo para el algoritmo.

Veamos un enfoque mixto, usaremos como Pivote el elemento central de la lista inicialmente, pero conforme avancemos lo podemos ir variando si encontramos uno mas adecuado. Podemos cambiar el uso del central por uno aleatorio sin problemas.

ALGORITMO PROCedure Qsort (arreglo,sentido,primero,ultimo)
     izquierda ← primero
     derecha ← ultimo
     pivote ← INT((primero + ultimo) / 2) 

     MIENTRAS (izquierda <= pivote) Y (derecha >= pivote)
       MIENTRAS (izquierda <= pivote) Y (arreglo(izquierda) < arreglo(pivote))
         izquierda ← izquierda + 1
       FIN MIENTRAS
       MIENTRAS (derecha >= pivote) Y (arreglo(derecha) > arreglo(pivote))
         derecha ← derecha - 1
       FIN MIENTRAS
       
       INTERCAMBIA_ELEMENTOS(izquierda, derecha)
       
       izquierda ← izquierda + 1
       derecha ← derecha - 1
       SI (izquierda - 1) = pivote ENTONCES 
         derecha ← derecha + 1
         pivote ← derecha
       SI NO
         SI (derecha + 1) = pivote ENTONCES
           izquierda ← izquierda - 1
           pivote ← izquierda
         FIN SI
       FIN SI 
     FIN MIENTRAS
     
     SI (primero < pivote-1) ENTONCES 
       QsortM arreglo,sentido,primero ,pivote-1,aleatorio
     FIN SI 
     SI (ultimo > pivote+1) ENTONCES 
       QsortM arreglo,sentido,pivote+1,ultimo  ,aleatorio
     FIN SI 

Como vemos el algoritmo es casi el mismo, cambia el que estemos usando desde el principio el valor del pivote para la división de las sublistas, en lugar de buscar el punto de cruce para elegir uno, y luego ya lo usaremos o cambiaremos segun lo que nos vamos encontrando. En la implementación uso una pequeña mejora, si la sublista tiene dos elementos, directamente los compare y busco su orden en lugar de meterme en el algoritmo de nuevo.

15140 DEFine PROCedure Rapida_Medio (arreglo,sentido,primero,ultimo,aleatorio)
15150   IF ultimo=0 THEN ultimo=DIMN(arreglo)
15160   QsortM arreglo, sentido, primero, ultimo,aleatorio
15170 END DEFine 
15180 :
15190 :
15200 DEFine PROCedure QsortM (arreglo,sentido,primero,ultimo,aleatorio)
15210   LOCal pivote,izquierda,derecha
15220   :
15230   IF (primero+1 = ultimo) THEN 
15240     IF compara(arreglo(primero),arreglo(ultimo),sentido,No) THEN 
15250       SWAP arreglo(primero),arreglo(ultimo)
15260     END IF 
15270   ELSE 
15280     izquierda = primero
15290     derecha = ultimo
15291     if aleatorio then
15292       pivote = rnd(primero,ultimo)
15293     else
15300       pivote = INT((primero + ultimo) / 2)
15301     end if
15310     :
15320     REPeat r1
15330       IF (izquierda > pivote) OR (derecha < pivote) THEN EXIT r1
15340       REPeat r2
15350         IF (izquierda > pivote) THEN EXIT r2
15360         IF compara(arreglo(izquierda),arreglo(pivote),sentido,Si)
15370           EXIT r2
15380         END IF 
15390         izquierda = izquierda + 1
15400       END REPeat r2
15410       REPeat r3
15420         IF (derecha < pivote) THEN EXIT r3
15430         IF compara(arreglo(derecha),arreglo(pivote),NOT sentido,Si)
15440           EXIT r3
15450         END IF 
15460         derecha = derecha - 1
15470       END REPeat r3
15480       SWAP arreglo(izquierda), arreglo(derecha)
15490       izquierda = izquierda + 1
15500       derecha = derecha - 1
15510       IF (izquierda - 1) = pivote THEN 
15520         derecha = derecha + 1
15530         pivote = derecha
15540       ELSE IF (derecha + 1) = pivote THEN 
15550         izquierda = izquierda - 1
15560         pivote = izquierda
15570       END IF 
15580     END REPeat r1
15590     IF (primero < pivote-1) THEN 
15600       QsortM arreglo,sentido,primero ,pivote-1,aleatorio
15610     END IF 
15620     IF (ultimo > pivote+1) THEN 
15630       QsortM arreglo,sentido,pivote+1,ultimo  ,aleatorio
15640     END IF 
15650   END IF 
15660 END DEFine 

Se usa una función para comparar y otra para intercambiar valores, he modificado los algoritmos para que todos las usen, así simplifico su código y hago que la comparación sea posible entre todos al usar la misma llamada siempre, ver el código de las funciones de intercambio iterativas que adjunto al final.

3371 Remar ----------------------------------------
3372 Remar -- Intercambia dos valores            --
3373 Remar ----------------------------------------
3380 DEFine PROCedure SWAP (a,b)
3390   :: nromovi(nrutina,nropaso)=nromovi(nrutina,nropaso)+3
3400   t=a
3410   a=b
3420   b=t
3430 END DEFine 
3440 :
3450 :
3460 Remar ----------------------------------------
3470 Remar -- FUNCION que compara dos números    --
3480 Remar --   a,b     -> Numeros a comparar    --
3490 Remar --   sentido -> 0=Ascendente          --
3500 Remar --   igual   -> Si es por igual o no  --
3510 Remar ----------------------------------------
3520 DEFine FuNction compara(a,b,sentido,igual)
3530   :: nrocomp(nrutina,nropaso)=nrocomp(nrutina,nropaso)+1
3540   IF igual THEN 
3550     IF sentido=Ascendente THEN 
3560       IF a >= b THEN RETurn Si
3570     ELSE 
3580       IF a <= b THEN RETurn Si
3590     END IF 
3600   ELSE 
3610     IF sentido=Ascendente THEN 
3620       IF a > b THEN RETurn Si
3630     ELSE 
3640       IF a < b THEN RETurn Si
3650     END IF 
3660   END IF 
3670   :
3680   RETurn No
3690 END DEFine 

La comparación entre los tres algoritmos nos da cifras muy buenas para el caso medio, como vemos casi iguales en todos, pero el buscar el puntero de forma dinámica desde el principio ralentiza el algoritmo en los casos mejor y peor, ya que tiende a producir muchas sublistas de 1 solo elemento.



Aquí tenéis los nuevos módulos, he cambiado un poco algunas cosas, por ejemplo en el proceso base he incluido la línea 1 GOTO 1000 que consigue que haciendo un RUN todo funcione sin necesidad de borrar las líneas del proceso de carga. Para que funcione cargar y ejecutar el fichero om_carga.

Programación del Sinclair QL (X): Ordenación por intercambio recursivo, Quicksort

Índice de entradas sobre programación del Sinclair QL

---

El mejor es hijo del peor

El mejor algoritmo de ordenación es una variante de la Burbuja, solo que intenta mover los elementos lo mas cerca posible de su ubicación definitiva en lugar de moverlos una posición a la vez, por lo que reduce los intercambios al mínimo.

El algoritmo lo que hace es tomar un elemento de la lista como un pivote. Luego mueve todos los elementos de forma que los de su izquierda sean todos menores que el pivote, y los de su derecha sean todos mayores que el pivote, creando dos sublistas que se pueden ordenar independientemente.

Una vez elegido el pivote se usan dos índices, uno recorre la lista desde su inicio hacia el final buscando un elemento que sea mayor que el pivote, luego se recorre con otro puntero desde el último hacia el inicio buscando uno que sea menor que el pivote, una vez localizados los intercambia. Se siguen buscando elementos de la misma manera hasta que se crucen los punteros. De esta forma se reduce al máximo los intercambios que son una parte muy pesada del algoritmo.

El resultado es que tenemos una sublista izquierda de elementos menores que el pivote, el pivote colocado en su lugar definitivo, y otra sublista derecha de elementos mayores que el pivote. Como ambas sublistas son independientes podemos llamar de manera recursiva al algoritmo con cada una de ellas para que las ordene a su vez. El pivote no tiene porque estar incluido en la lista, ya que lo que pretendemos es obtener dos sublistas.

La elección del pivote es importante para intentar optimizar al máximo el algoritmo, si se eligen mal el algoritmo se ralentiza mucho por lo que el objetivo es que las dos sublistas sean del mismo tamaño, contra mas equilibrado esté mejor eficiencia tendrá el algoritmo. Supongamos que tenemos esta lista [2,5,1,9,7] y vamos a buscar un pivote:

• El optimo sería el 5 que resultaría en dos pasos [2,1] [5] [9,7] ⇨ [1] [2] [5] [7] [9], pero sin analizar los datos no podemos conocer que ese es el mejor elemento.
• Primer elemento, 2 en el ejemplo: [1] [2] [5,9,7] ⇨ [1] [2] [5] [9,7] ⇨ [1] [2] [5] [7] [9]
• Ultimo elemento, 7 en el ejemplo: [2,5,1] [7] [9] ⇨ [1] [2,5] [7] [9] ⇨ [1] [2] [5] [7] [9]
• Elemento central, 1 en el ejemplo: [-] [1] [2,5,9,7] ⇨ [1] [2] [5] [9,7] ⇨ [1] [2] [5] [7] [9]

Como vemos aunque el ejemplo es muy sencillo solo eligiendo un buen elemento como pivote se optimizan los pasos. Se han buscado varios sistemas para localizar los pivotes, todos pensando que tras los primeros pasos del algoritmo las listas están ya bastante ordenadas:

• El sistema mas sencillo es usar el elemento central de la lista, en el ejemplo sería usar como pivote el [1] que hemos visto está lejos de la mejor opción, pero tras varias pasadas se aproximaría bastante. También podemos elegir un elemento al azar, esta técnica es sencilla de usar y elegir un elemento cualquiera aunque no lo parezca da buenos resultados en general, el azar tiende a compensar las cosas.
• Lo mejor sería usar el valor medio que es 4'8, y en nuestro ejemplo queda [2,1] [5,9,7] ⇨ [1] [2] [5] [7] [9], pero su cálculo con muchos elementos ralentiza el algoritmo. Una variante es pensar que la lista esta bastante ordenada, lo que hemos visto que es cierto tras los primeros pasos del algoritmo, y tomar tres elementos de la lista calculando su media. Los elementos serían primero, central y ultimo. En nuestro ejemplo sería (2+1+7)/3 = 3'33 que también es buen valor.
• El medio mas usado es un pivote variable, se comparan los elementos a izquierda y derecha hasta que haya que intercambiarlos, cambiando el pivote en ese momento, y se sigue comparando y cambiando el pivote, hasta que se crucen los índices, momento en que el elemento que marcan será el pivote.

ALGORITMO Qsort (lista,sentido[Ascendente|Descendente],primero,ultimo)

  izquierda ← primero
  derecha ← ultimo
  pivote ← izquierda

  REPETIR
    SI ((sentido = Ascendente) Y (lista(izquierda) > lista(derecha))) O BIEN
       ((sentido = Descendente) Y (lista(izquierda) < lista(derecha))) ENTONCES

      INTERCAMBIA_ELEMENTOS(izquierda,derecha)
      SI pivote = izquierda ENTONCES
        izquierda ← izquierda+1
        pivote ← derecha
      SI NO
        derecha ← derecha-1
        pivote ← izquierda
      FIN SI
    SI NO
      SI pivote = izquierda ENTONCES
        derecha ← derecha-1
      SI NO
        izquierda ← izquierda+1
      FIN SI
    FIN SI
  HASTA QUE izquierda >= derecha

  SI primero <> pivote ENTONCES
    qsort arreglo, primero, pivote-1
  FIN SI
  SI ultimo <> pivote ENTONCES
    qsort arreglo, pivote+1, ultimo
  FIN SI

Para mejorar la velocidad del algoritmo hay que reducir las llamadas recursivas, para lo que se suele emplear un enfoque mixto, en lugar de iterar hasta el final hacerlo hasta que las sublistas sean de pocos elementos, pueden ser entre 5 y 10 en máquinas lentas, o llegar al centenar en rápidas, y luego aplicar otro sistema de ordenación a los resultados que ya están casi ordenados, usualmente se usa la inserción. Pero voy con la rutina de Qsort hasta el final, para que sea comparable:

14130 DEFine PROCedure Rapida (arreglo,sentido,primero,ultimo)
14140   IF ultimo=0 THEN ultimo=DIMN(arreglo)
14150   Qsort arreglo, sentido, primero, ultimo
14160 END DEFine
14170 :
14180 :
14190 DEFine PROCedure Qsort (arreglo,sentido,primero,ultimo)
14200   LOCal repetir, izquierda, derecha, pivote
14210   :
14220   izquierda = primero
14230   derecha = ultimo
14240   pivote = primero
14250   :
14260   REPeat repetir
14270     IF izquierda >= derecha : EXIT repetir
14280     :
14290     :: nrocomp(nrutina,nropaso)=nrocomp(nrutina,nropaso)+1
14300     cambiar=No
14310     IF sentido=Ascendente THEN
14320       IF arreglo(izquierda) > arreglo(derecha) THEN cambiar=Si
14330     ELSE
14340       IF arreglo(izquierda) < arreglo(derecha) THEN cambiar=Si
14350     END IF
14360     IF cambiar THEN
14370       :: nromovi(nrutina,nropaso)=nromovi(nrutina,nropaso)+3
14380       temp = arreglo(izquierda)
14390       arreglo(izquierda) = arreglo(derecha)
14400       arreglo(derecha) = temp
14410       :
14420       IF pivote = izquierda
14430         izquierda = izquierda+1
14440         pivote = derecha
14450       ELSE
14460         derecha = derecha-1
14470         pivote = izquierda
14480       END IF
14490     ELSE
14500       IF pivote =izquierda
14510         derecha = derecha -1
14520       ELSE
14530         izquierda = izquierda+1
14540       END IF
14550     END IF
14560   END REPeat repetir
14570   :
14580   IF primero <> pivote THEN
14590     Qsort arreglo, sentido, primero, pivote-1
14600   END IF
14610   IF ultimo <> pivote THEN
14620     Qsort arreglo, sentido, pivote+1, ultimo
14630   END IF
14640 END DEFine Qsort

Resultado del QuickSort

En el caso medio el resultado es espectacular en comparación con la burbuja y sus variantes para 200 elementos, ya que en comparación con los 9 minutos y 48 segundos de la variante mas rápida que es la sacudida, con 13227 comparaciones y 28956 intercambios, pasamos a 1minuto y 39 segundos, con 2046 comparaciones y 1362 intercambios. Cuando la lista está ordenada o en orden inverso el resultado ya no es tan bueno, aunque sigue siendo mejor que la burbuja.

Programación del Sinclair QL (IX): Ordenación por intercambio iterativo, variantes de la Burbuja

Índice de entradas sobre programación del Sinclair QL

---

Mejoras a la ordenación por Burbuja. Tortugas y liebres

Seguimos dando vueltas a la Burbuja, buscando optimizarla al máximo. Adelanto que es una búsqueda vana, como indican todos los autores Burbuja nunca será un método óptimo, no puede competir con la Ordenación por Inserción que es también un algoritmo sencillo, y mucho menos con el QuickSort.

Cuando lanzamos la ordenación por Burbuja los elementos mayores van rápidamente al final de la lista por lo que se les denomina liebres, mientras que los elementos mas pequeños suben poco a poco hacia su posición por lo que se les denomina tortugas. Existen una serie de variantes de la Burbuja que intentan convertir las tortugas en liebres para que se acelere el proceso. Se usan en general dos técnicas, una es cambiar la dirección del recorrido para ir subiendo y bajando por los elementos de la lista, y la otra es intercambiar elementos separados y no cercanos.

Ordenación por Sacudida, cambiando la dirección en cada pasada

La Ordenación por Sacudida, Burbuja Bidireccional o Cocktail Sort es una variante que en cada pasada cambia el sentido en que recorre la lista, de forma que cuando llega al final empieza a recorrerla de mayor a menor ubicando en ese momento el menor elemento el primero. Ahora vuelve a empezar pero recorriendo la lista del elemento 2 al penúltimo en ida y vuelta. De esta manera en cada cambio de sentido las tortugas se convierten en liebres y viceversa.

ALGORITMO Sacudida (lista,sentido[Ascendente|Descendente],primero,ultimo)
 
  izquierda ← primero
  derecha ← ultimo-1

  REPETIR
    // --> Burbuja hacia la derecha
    ordenada ← cierto
    BUCLE i DESDE izquierda HASTA derecha
      SI (sentido = Ascendente)  Y (lista(i) < lista(i+1)) O BIEN
         (sentido = Descendente) Y (lista(i) > lista(i+1)) ENTONCES
  
        INTERCAMBIA_ELEMENTOS(i, i+1)
        ordenada ← falso
        ultimo ← i 
      FIN SI
    FIN BUCLE_PARA
    izquierda ← izquierda+1
    derecha ← ultimo
    SI ordenada O BIEN (izquierda>derecha) ENTONCES
      FIN_REPETIR 
    FIN SI 

    // <-- b="" burbuja="" cierto="" hacia="" izquierda="" la="" ordenada="">BUCLE

i DESDE derecha HASTA izquierda cambiar ← falso SI (sentido = Ascendente) Y (lista(i-1) < lista(i)) O BIEN (sentido = Descendente) Y (lista(i-1) > lista(i)) ENTONCES INTERCAMBIA_ELEMENTOS(i-1, i) ordenada ← falso ultimo ← i FIN SI FIN BUCLE_PARA izquierda ← primero derecha ← derecha-1 SI ordenada O BIEN (izquierda>derecha) ENTONCES FIN_REPETIR FIN SI
Esta versión mejora el proceso en el caso medio pero solo si hay bastantes elementos a ordenar, si son pocos elementos, si la lista está casi ordenada o está en orden inverso o casi invertido los tiempos son los mismos que para la burbuja. Veamos el código en SuperBASIC.

01 DEFine PROCedure Sacudida (arreglo,sentido,primero,ultimo)
02   LOCal izquierda,derecha,cambiar,ordenada,repetir,i
03   :
04   IF ultimo=0 THEN ultimo=DIMN(arreglo)
05   izquierda=primero
06   derecha=ultimo-1
07   :
08   REPeat repetir
09     :
10     REMark Bucle hacia la derecha
11     :
12     ordenada=Si
13     FOR i=izquierda TO derecha
14       cambiar=No
15       :: nrocomp(nrutina,nropaso)=nrocomp(nrutina,nropaso)+1
16       IF sentido=Ascendente THEN 
17         IF arreglo(i) > arreglo(i+1) THEN cambiar=Si
18       ELSE 
19         IF arreglo(i) < arreglo(i+1) THEN cambiar=Si
20       END IF 
21       IF cambiar THEN 
22         :: nromovi(nrutina,nropaso)=nromovi(nrutina,nropaso)+3
23         temp         = arreglo(i)
24         arreglo(i)   = arreglo(i+1)
25         arreglo(i+1) = temp
26         :
27         ordenada=No
28         ultimo=i
29       END IF 
30     END FOR i
31     izquierda=izquierda+1
32     derecha=ultimo
33     IF ordenada OR (izquierda>derecha) THEN EXIT repetir
34     :
35     REMark Bucle hacia la izquierda
36     :
37     ordenada=Si
38     FOR i=derecha TO izquierda STEP -1
39       cambiar=No
40       :: nrocomp(nrutina,nropaso)=nrocomp(nrutina,nropaso)+1
41       IF sentido=Ascendente THEN 
42         IF arreglo(i-1) > arreglo(i) THEN cambiar=Si
43       ELSE 
44         IF arreglo(i-1) < arreglo(i) THEN cambiar=Si
45       END IF 
46       IF cambiar THEN 
47         :: nromovi(nrutina,nropaso)=nromovi(nrutina,nropaso)+3
48         temp         = arreglo(i-1)
49         arreglo(i-1) = arreglo(i)
50         arreglo(i)   = temp
51         :
52         ordenada=No
53         primero=i
54       END IF 
55     END FOR i
56     izquierda=primero
57     derecha=derecha-1
58     IF ordenada OR (izquierda > derecha) THEN EXIT repetir
59   END REPeat repetir
60 END DEFine 

Ordenación por Cremallera, cambiando tortugas por liebres

La Ordenación de cremallera,  conocida como Gnome Sort (ordenación de los nomos) o Stupid Sort (ordenación tonta), usa también la táctica de cambiar de dirección pero lo hace continuamente intentando localizar lo mas rápido posible una tortuga, para convertirla en liebre y moverla rápido hacia su lugar. El algoritmo empieza comparando las parejas de valores, si están en orden avanza a la siguiente pareja, pero si no están en orden, se intercambian entre si, y ahora se cambia de sentido, se reduce el puntero y se compara en dirección contraria hasta que haya un intercambio o se alcance el inicio del arreglo. El proceso se detiene cuando se alcanza el final del arreglo. Así va trabajando buscando tortugas y moviendo liebres.

ALGORITMO Cremallera (lista,sentido[Ascendente|Descendente],primero,ultimo) 

  i ← primero + 1
  MIENTRAS i < ultimo
    SI (sentido = Ascendente)  Y (lista(i-1) <= lista(i)) O BIEN
       (sentido = Descendente) Y (lista(i-1) >= lista(i)) ENTONCES
      i ← i + 1
    SI NO
      INTERCAMBIA_ELEMENTOS(i-1, i)
      SI i > primero + 1 ENTONCES
        i ← i - 1
      FIN SI
    FIN SI
  FIN MIENTRAS

Como vemos, el algoritmo tiene la ventaja de ser muy sencillo, y en un lenguaje interpretado como nuestro SuperBASIC es importante la sencillez para mejorar la velocidad, pero tampoco es un algoritmo rápido.

630 DEFine PROCedure Cremallera (arreglo,sentido,primero,ultimo)
640   LOCal cambiar,repetir,i
650   :
660   IF ultimo=0 THEN ultimo=DIMN(arreglo)
670   :
680   i=primero+1
690   REPeat repetir
700     IF i > ultimo THEN EXIT repetir
710     :
720     :: nrocomp(nrutina,nropaso)=nrocomp(nrutina,nropaso)+1
730     cambiar=No
740     IF sentido=Ascendente THEN 
750       IF arreglo(i-1) > arreglo(i) THEN cambiar=Si
760     ELSE 
770       IF arreglo(i-1) < arreglo(i) THEN cambiar=Si
780     END IF 
790     IF NOT cambiar THEN 
800       i=i+1
810     ELSE 
820       :: nromovi(nrutina,nropaso)=nromovi(nrutina,nropaso)+3
830       temp         = arreglo(i-1)
840       arreglo(i-1) = arreglo(i)
850       arreglo(i)   = temp
860       :
870       IF i > primero+1 THEN i=i-1
880     END IF 
900   END REPeat repetir
910 END DEFine

Ordenación por Peine, cambiando elementos separados

La ordenación por Peine o Comb Sort utiliza la técnica de comparar elementos no correlativos sino separados entre sí, de esta forma movemos grupos de elementos en la dirección adecuada, en lugar de posicionar solo un elemento en cada vez. La técnica es muy simple, se calcula un valor de distanciamiento entre elementos, inicialmente tomando la parte entera de dividir el número de elementos entre 1.3 (valor que se ha calculado experimentalmente como el mejor, aunque el valor teórico es de 1.2473). Se recorre la lista de elementos, comparando los valores separados por ese incremento en lugar de comparar los contiguos, intercambiándolos si es necesario, hasta que no se necesiten mas intercambios. Luego se vuelve a tomar como separación entre elementos la parte entera de dividir el valor anterior por 1.3, y se repite el proceso, hasta que la distancia es 1 y se convierte en una burbuja ordinaria. En cada pasada los elementos están un poco mas ordenados, y sobre todo mas cercanos a su lugar definitivo, evitando mover los elementos muchas posiciones a lo largo de la lista.

Su creador es Włodzimierz Dobosiewicz en 1980, pero en un articulo publicado originalmente en la revista BYTE en 1991 por Stephen Lacey y Richard Box, argumentan que cuando la distancia es 9 o 10 se optimiza el algoritmo cambiando el factor a 11, a esta variante la llamaron Combsort11, lo que es el trozo en color naranja del siguiente algoritmo:

ALGORITMO Peine (lista,sentido[Ascendente|Descendente],primero,ultimo)

  distancia ← ultimo - primero + 1  
  factor ← 1.3                      

  REPETIR
    distancia ← TOMAR_PARTE_ENTERA(distancia / factor)
    SI (distancia = 9) O BIEN (distancia = 10) ENTONCES
      distancia ← 11
    FIN SI
    SI distancia < 1 ENTONCES
      distancia ← 1
    FIN SI
    
    ordenado ← Cierto
    derecha ← primero
    BUCLE PARA i DESDE primero HASTA ultimo - distancia
      SI (sentido = Ascendente)  Y (lista(i) > lista(i+distancia)) O BIEN
         (sentido = Descendente) Y (lista(i) < lista(i+distancia)) ENTONCES    
             
        INTERCAMBIA_ELEMENTOS(i, i+distancia)
        ordenado ← Falso
        derecha ← i
      FIN SI
    FIN BUCLE PARA
    SI distancia = 1 ENTONCES
      ultimo ← derecha
    FIN SI
         
  HASTA QUE (distancia = 1) Y ordenado

Estos valores de 11 en lugar de 9 o 10, igual que el de 1.3 como mejor factor, se han calculado teóricamente y comprobado experimentalmente usando listas de miles de elementos, si nuestras listas son pequeñas no se alcanzan diferencias pues el aumentar la complejidad del algoritmo reduce sus ventajas.

130 DEFine PROCedure Peine (arreglo,sentido,primero,ultimo)
140   LOCal distancia,factor,derecha,cambiar,ordenada,repetir,i
150   :
160   IF ultimo=0 THEN ultimo=DIMN(arreglo)
170   :
180   distancia=ultimo-primero+1
190   factor=1.3
200   REPeat repetir
210     distancia=INT(distancia/factor)
220     IF (distancia=9) OR (distancia=10) THEN distancia=11
230     IF distancia < 1 THEN distancia = 1
240     :
250     ordenada=Si
260     derecha=primero
270     FOR i=primero TO ultimo-distancia
280       cambiar=No
290       :: nrocomp(nrutina,nropaso)=nrocomp(nrutina,nropaso)+1
300       IF sentido=Ascendente THEN 
310         IF arreglo(i) > arreglo(i+1) THEN cambiar=Si
320       ELSE 
330         IF arreglo(i) < arreglo(i+1) THEN cambiar=Si
340       END IF 
350       IF cambiar THEN 
360         :: nromovi(nrutina,nropaso)=nromovi(nrutina,nropaso)+3
370         temp         = arreglo(i)
380         arreglo(i)   = arreglo(i+1)
390         arreglo(i+1) = temp
400         :
410         ordenada=No
420         derecha=i
430       END IF 
440     END FOR i
450     IF distancia=1 THEN 
460       IF ordenada THEN EXIT repetir
470       ultimo=derecha
480     END IF 
490   END REPeat repetir
500 END DEFine 

Pares o nones ¿jugando a ordenar?

La Ordenación Impar-Par es usada sobre todo en su variante para procesamiento paralelo, es una burbuja en la que en una primera pasada se recorren los elementos impares de la lista, y en una segunda se recorre por los elementos pares, por tanto el algoritmo es muy parecido al de la sacudida, pero sin cambiar el sentido. No aporta nada, pero si tenemos la posibilidad de usar varios procesadores es un algoritmo sencillo para repartir entre todos la carga.

ALGORITMO Impar_Par (lista,sentido[Ascendente|Descendente],primero,ultimo)

  REPETIR
    ordenada ← cierto
    
    // Burbuja de impares
    BUCLE i DESDE 1 HASTA ultimo-1 SUMANDO 2
      SI (sentido = Ascendente)  Y (lista(i) < lista(i+1)) O BIEN
         (sentido = Descendente) Y (lista(i) > lista(i+1)) ENTONCES
  
        INTERCAMBIA_ELEMENTOS(i, i+1)
        ordenada ← falso
      FIN SI
    FIN BUCLE_PARA

    // Burbuja de pares
    BUCLE i DESDE 0 HASTA ultimo-1 SUMANDO 2
      SI (sentido = Ascendente)  Y (lista(i) < lista(i+1)) O BIEN
         (sentido = Descendente) Y (lista(i) > lista(i+1)) ENTONCES
         
        INTERCAMBIA_ELEMENTOS(i, i+1)
        ordenada ← falso
       FIN SI
    FIN BUCLE_PARA
    SI ordenada ENTONCES
      FIN_REPETIR 
    FIN SI 

Este algoritmo no aporta mucho, solo lo desarrollo por completar las variantes. En lugar de dos bucles independientes, por simplificar uso dos bucles anidados, en primero recorre solo 1 y 0 que son los inicios de los dos bucles.

130 DEFine PROCedure Impar_par (arreglo,sentido,primero,ultimo)
140   LOCal cambiar,ordenada,repetir,i,j
150   :
160   IF ultimo=0 THEN ultimo=DIMN(arreglo)
170   :
180   REPeat repetir
190     ordenada=Si
200     FOR j=1 TO 0 STEP -1
210       FOR i=j TO ultimo-1 STEP 2
220         cambiar=No
230         :: nrocomp(nrutina,nropaso)=nrocomp(nrutina,nropaso)+1
240         IF sentido=Ascendente THEN 
250           IF arreglo(i) > arreglo(i+1) THEN cambiar=Si
260         ELSE 
270           IF arreglo(i) < arreglo(i+1) THEN cambiar=Si
280         END IF 
290         IF cambiar THEN 
300           :: nromovi(nrutina,nropaso)=nromovi(nrutina,nropaso)+3
310           temp         = arreglo(i)
320           arreglo(i)   = arreglo(i+1)
330           arreglo(i+1) = temp
340           :
350           ordenada=No
360         END IF 
370       END FOR i
380     END FOR j
390     IF ordenada THEN EXIT repetir
400   END REPeat repetir
410 END DEFine 

Comparativa final de resultados con algoritmos de intercambio

El resultado final de la comparativa es muy poco alentador. Partiendo de la base de que todos los algoritmos acaban intercambiando el mismo número de elementos (como es lógico pues al final siempre usan el mismo sistema), el algoritmo mas rápido será el que menos comparaciones requiera, otro valor que es similar en todos los algoritmos ya que se basan en el mismo principio. Con 200 elementos y sumando los tiempos de las tres ordenaciones de la prueba, vemos este resultado:

• 29 minutos 31 segundos Burbuja
• 26 minutos 27 segundos Sacudida
• 44 minutos 40 segundos Cremallera
• 33 minutos 35 segundos Peine
• 28 minutos 55 segundos Impar-Par

Al final vemos que el mejor sistema es el de sacudida, ya que obtiene el mejor tiempo en el caso medio, no se alarga en el mejor y obtiene un buen puesto en el peor caso, aunque veremos que el método de inserción, que es un sencillo algoritmo iterativo que requiere menos comparaciones y movimientos de datos gana por goleada a nuestra Burbuja, pero aun así se ve superado por el QuickSort, basado también en intercambios pero recursivo.

Programación del Sinclair QL (VIII): Ordenación por intercambio iterativo, Burbuja

 Índice de entradas sobre programación del Sinclair QL

---

Ordenación por burbuja

Este sistema, denominado en inglés Bubblesort, es el sistema mas sencillo de entender aunque también es el algoritmo mas lento e ineficiente de todos, por lo que en muchos libros se recomienda ni siquiera enseñarlo en los cursos de programación. A pesar de esto comienzo por el que todos hemos empezado, aunque recomiendo usar Inserción como algoritmo iterativo y Quicksort como recursivo que son mucho mas eficientes.

La idea del algoritmo es sencilla, se recorre la lista comparando cada elemento con el siguiente, si este es menor se intercambian ambos elementos. Este proceso se repite hasta que la lista esté ordenada, con cada pasada los elementos mayores se hunden en la lista rápidamente, moviendo hacia arriba los elementos ligeros mas lentamente, como burbujas en un líquido, de ahi su nombre. Vamos con el algoritmo en seudo-código que orden por burbuja una lista, indicando el primer y ultimo elemento de la misma que deseamos ordenar

ALGORITMO Burbuja (lista,primero,ultimo) 
 
  REPETIR
    BUCLE i DESDE primero HASTA ultimo-1
      SI lista(i) > lista(i+1) ENTONCES
        INTERCAMBIA(i, i+1)
      FIN SI
    FIN BUCLE
  HASTA QUE lista_ordenada 

Como vemos es un bucle que se repite recorriendo la lista de elementos, intercambiándolos si es necesario, hasta que la lista esté ordenada. ¿Como sabemos cuando lo está? hay dos sistemas complementarios. El primero es darse cuenta de que cuando en una pasada no sean necesarios mas intercambios, la lista está ordenada. Se usa una variable auxiliar para ello a la que se le denomina centinela, y al algoritmo en general Burbuja con centinela.

ALGORITMO Burbuja (lista,primero,ultimo) 
 
  REPETIR
    ordenada ← cierto
    BUCLE i DESDE primero HASTA ultimo-1
      SI lista(i) > lista(i+1) ENTONCES
        INTERCAMBIA(i, i+1)
        ordenada ← falso
      FIN SI
    FIN BUCLE
  HASTA QUE ordenada 

La otra forma es conocer cuantas pasadas necesitamos, lo que es también sencillo aunque en principio no lo parezca. Sabemos que en cada pasada el último elemento está siempre posicionado, por lo que debemos hacer tantas pasadas como elementos en la lista. Pero como sabmos que tras una pasada el último elemento está ordenado, también podemos reducir el recorrido en uno. Debemos repetir hasta que hayamos reducido la lista a un elemento. Como el método es complementario al anterior, usaremos ambos a la vez.

ALGORITMO Burbuja (lista,primero,ultimo) 
 
  REPETIR
    ordenada ← cierto
    BUCLE i DESDE primero HASTA ultimo-1
      SI lista(i) > lista(i+1) ENTONCES
        INTERCAMBIA(i, i+1)
        ordenada ← falso
      FIN SI
    FIN BUCLE
    ultimo ← ultimo - 1
  HASTA QUE (ordenada) O BIEN (ultimo=primero) 

Aun podemos añadir una optimización adicional. Cuando movemos un elemento puede que llegue a un punto en que los elementos a su derecha sean todos mayores que él, por lo que sabemos que esa parte ya está ordenada. Así por ejemplo si tenemos 30,12,10,40,50 y lanzamos el proceso, el 30 solo lo movemos 2 veces, quedando la lista como 12,10,30,40,50 y sabemos que en la siguiente pasada en lugar de reducir solo en uno podemos reducir en tres directamente. Como esto es nuevamente complementario lo usamos todo a la vez. No podemos alterar directamente el valor de la variable que marca el último directamente, ya que es la que se usa de compración en el bucle. Hay lenguajes como el C en que este cambio altera el bucle, y otros como el SuperBASIC en que no, como esto es un algoritmo genérico debemos pensar que puede ser alterado, y usaremos una variable auxiliar.

ALGORITMO Burbuja (lista,primero,ultimo) 
 
  REPETIR
    ordenada ← cierto
    derecha ← primero
    BUCLE i DESDE primero HASTA ultimo-1
      SI lista(i) > lista(i+1) ENTONCES
        INTERCAMBIA(i, i+1)
        ordenada ← falso
        derecha ← i
      FIN SI
    FIN BUCLE
    ultimo ← derecha
  HASTA QUE (ordenada) O BIEN (ultimo=primero) 

Se puede reempazar el bucle REPETIR por un FOR, lo que hace este algoritmo compatible con otras versiones de BASIC que no soportan esta sentencia, con dos variantes equivalentes:

FOR i = ultimo-1 TO primero STEP -1
  FOR j = primero TO i-1

O bien

FOR i = primero+1 TO ultimo
  FOR j = primero TO ultimo-i

Solo resta un detalle, el algoritmo puede ordenar de menor a mayor o al contrario, solo es necesario cambiar el sentido de la comparación, para ello añadimos como parámetro el sentido en que deseamos ordenar, y cambiamos la comparación.

ALGORITMO Burbuja (lista,sentido[Ascendente|Descendente],primero,ultimo) 
 
  REPETIR
    ordenada ← cierto
    derecha ← primero
    BUCLE i DESDE primero HASTA ultimo-1
      SI (sentido = Ascendente)  Y (lista(i) > lista(i+1)) O BIEN
         (sentido = Descendente) Y (lista(i) < lista(i+1)) ENTONCES
        INTERCAMBIA(i, i+1)
        ordenada ← falso
        derecha ← i
      FIN SI
    FIN BUCLE
    ultimo ← derecha
  HASTA QUE (ordenada) O BIEN (ultimo=primero) 

Con esto ya podemos transcribir el algoritmo a SuperBASIC. Un tema que ocurre demasiado a los programadores es que una vez tienen su algoritmo, en lugar de transcribirlo en su lenguaje, lo escriben de nuevo, lo que es un esfuerzo inútil cuando todo ha sido estudiado de antemano. Aquí está mi transcripción del programa, en el que lo único que añado es que por temas de hacer las líneas mas cortas, como SuperBASIC no admite sentencias en varias líneas, uso una variable auxiliar para saber si tengo que intercambiar los elementos, y la asigno según desee que la lista sea ascendente o descendente, y que si no indico cual es el último elemento que deseo ordenar, lo calculo en función de los elementos del arreglo:

4000 REMark ---------------------------------------------
4010 REMark -- ALGORITMOS DE ORDENACION                --
4020 REMark --   Modulo....: Burbuja                   --
4030 REMark --   Objetivo..: Ordena un arreglo por el  --
4040 REMark --               algoritmo de burbuja      --
4050 REMark --   Autor.....: javu61, 11/2016           --
4060 REMark --   Parametros:                           --
4070 REMark --     arreglo -> Arreglo a ordenar        --
4080 REMark --     sentido -> FALSO = Ascendente       --
4090 REMark --     primero -> primer elemento          --
4100 REMark --     ultimo  -> ultimo elemento          --
4110 REMark --                Si ultimo=0 -> Todos     --
4120 REMark ---------------------------------------------
4130 DEFine PROCedure Burbuja (arreglo,sentido,primero,ultimo)
4140   LOCal derecha,cambiar,ordenada,repetir,i
4150   :
4160   IF ultimo=0 THEN ultimo=DIMN(arreglo)
4170   :
4180   REPeat repetir
4190     ordenada=Si
4200     derecha=primero
4210     FOR i=primero TO ultimo-1
4220       cambiar=No
4230       :: nrocomp(nrutina,nropaso)=nrocomp(nrutina,nropaso)+1
4240       IF sentido=Ascendente THEN 
4250         IF arreglo(i) > arreglo(i+1) THEN cambiar=Si
4260       ELSE 
4270         IF arreglo(i) < arreglo(i+1) THEN cambiar=Si
4280       END IF 
4290       IF cambiar THEN 
4300         :: nromovi(nrutina,nropaso)=nromovi(nrutina,nropaso)+3
4310         temp         = arreglo(i)
4320         arreglo(i)   = arreglo(i+1)
4330         arreglo(i+1) = temp
4340         :
4350         ordenada=No
4360         derecha=i
4370       END IF 
4380     END FOR i
4390     ultimo=derecha
4400     IF ordenada OR (primero=ultimo) THEN EXIT repetir
4410   END REPeat repetir
4420 END DEFine 

Las líneas que comienzan por :: son solo para contar comparaciones e intercambios, necesario solo para las pruebas, en el algoritmo definitivo hay que eliminar estas líneas para poder usarlo en otros programas.

Programación del Sinclair QL (VII): Algoritmos de ordenación, planteamiento para las pruebas

Índice de entradas sobre programación del Sinclair QL

---

Nota importante sobre los programas que se presenten

Incluiré el código completo del programa siempre al final de la entrada, pero a lo mejor veis que no coinciden los números de línea, e incluso que en la misma entrada los números de línea se solapan entre trozos del código.

Salvo en el módulo de carga en el resto del módulos no usan GOTO o GOSUB, aunque nunca es problema renumerarlos, ya que los números de línea solo sirven como referencia para la edición y los comentarios que haga, incluso puede que en algunos casos veáis que se solapan dentro del mismo articulo. Al final siempre encontrareis el código completo del mismo, podéis usarlo para vuestro QL o con vuestro emulador.

La base para las pruebas de algoritmos con datos en memoria

Empezaremos con lo básico para las pruebas de los algoritmos que es disponer de una estructura común para todos, que los llame con las mismas condiciones iniciales y guarde los resultados del proceso. En el QL hay un Reloj que podemos explotar bien desde código máquina, pero desde SuperBASIC solo tenemos posibilidad de contar segundos, es un poco limitado pero creo que bastará para las pruebas.

Voy a ordenar un arreglo de números de la longitud que le indiquemos, un procedimiento o función acepta un arreglo como parámetro de entrada, pero yo el arreglo no se lo puedo pasar al algoritmo como parámetro pues las variables se pasan por valor y lo que se ordenaría sería el arreglo copiado y no el original, es una limitación importante de no disponer de punteros.

El proceso lo voy a dividir en ficheros separados que cargaré usando MERGE, de esta forma es mas sencillo el mantenimiento, y tiene la ventaja de que cada módulo de ordenación es un fichero independiente, por lo que se puede usar en otros programas.

Módulo de carga

Este es el modulo que realizará la carga del resto, de forma que no hay que hacerlo manualmente nunca. Es muy sencillo pero hay que eliminarlo si se desea ejecutar el programa para que no lo vuelva a ejecutar, acuérdate de usar DLINE TO 999 cuando termine de cargar. Cada vez que incluyo un módulo debo cambiar la línea 170, y añadir dos líneas mas tras la 190 por cada módulo:

100 REMark ----------------------------------------
110 REMark -- ALGORITMOS DE ORDENACION --
120 REMark -- Modulo: Cargador de modulos --
130 REMark -- Autor.: javu61, noviembre 2016 --
140 REMark ----------------------------------------
150 :
160 :
170 DATA "mdv1_"
180 DATA "o_base" , "Modulo base"
190 DATA "o_selector" , "Modulo Selector"
200 DATA "o_burbuja" , "Modulo Burbuja"
210 DATA "o_sacudida" , "Modulo Sacudida"
220 DATA ""
230 :
240 actual = 0 : total = 0
250 DIM p$(20,2,20)
260 :
270 RESTORE 
280 READ u$
290 REPeat leer_data
300 READ p$(total,0) : IF p$(total,0)="" THEN EXIT leer_data
310 READ p$(total,1)
320 p$(total,0)=u$ & p$(total,0)
330 total=total+1
340 END REPeat leer_data
350 :
360 MODE 4 : PAPER 0 : CLS
370 PRINT "Cargando modulos del programa"
380 :
390 PRINT " (";actual;"/";total;") ";p$(actual,1)
400 MERGE p$(actual,0)
410 actual=actual+1
420 IF p$(actual,0) <> "" THEN GO TO 390
430 :
440 :
450 PRINT "Ejecute DLINE TO 999 antes de ejecutar"
460 STOP

En la línea 420 hay un GOTO, el único que encontrarás en el programa, está ya que al ejecutar la sentencia MERGE dentro de un bucle se pierden los punteros, hay que recurrir al método tradicional para que funcione.

Módulo base

Este es el modulo que realizará las pruebas de los algoritmos. Como veréis todo lo empiezo por una cabecera general con lo que es, no es necesario pero si una practica de buen programador. Una técnica para acelerar los programas en BASIC es eliminar comentarios, ya que el programa pasa por ellos y los debe analizar, esto no es necesario en SuperBASIC pues monta una tabla de procedimientos y funciones, por lo que casi nunca pasará por los comentarios.

1000 REMark ----------------------------------------
1010 REMark -- ALGORITMOS DE ORDENACION           --
1020 REMark --   Modulo: Base para las pruebas    --
1030 REMark --   Autor.: javu61, noviembre 2016   --
1040 REMark ----------------------------------------

Primero creo un manejador de errores, es una muy buena costumbre tener al menos una estándar, debe estar al principio para que el programa sepa que existe esa rutina de errores.

1060 REMark ----------------------------------------
1070 REMark -- Manejo de errores                  --
1080 REMark ----------------------------------------
1090 WHEN ERRor 
1100   PRINT "En la linea ";ERLIN;" se ha producido un error ";ERNUM;": ";
1110   REPORT #1,ERNUM
1120   STOP
1130 END WHEN 

Ahora voy lanzando procesos que hagan las cosas, contra mas modular mejor, pues es difícil seguir un programa largo y al dividirlo en partes pequeñas se simplifica su lectura, lo que para el mantenimiento es fundamental. Creo que fue Ole-Johan Dahl, uno de los creadores de la programación orientada a objetos, el que dijo que una función no debía ocupar mas de una página (supongo que de papel y no de pantalla). Empiezo borrando pantalla y pidiendo los elementos a ordenar, contra mas tenga mas tardará, y mejor resultado darán las prueba, pero el QL no es un veloz galgo, no os paséis.

1160 REMark ----------------------------------------
1170 REMark -- Pedir elementos a procesar         --
1180 REMark ----------------------------------------
1190 LET nroelem = 0    : REMark Nro elementos a ordenar
1200 :
1210 MODE 4 : PAPER 0 : CLS
1220 INPUT "Numero de elementos a ordenar: ";nroelem
1230 nroelem=nroelem - 1  : REMark Empieza en cero

A mi me gusta definir las variables siempre, ahorra errores, pero en SuperBASIC no es necesario ni posible mas que para los arreglos, pero lo simulo inicializándolas a un valor, y uso LET para distinguir que solo es la primera declaración. En SuperBASIC no existen las constates que hacen el código mas legible, las voy a simular con variables, todas son booleanas, en SuperBASIC cero equivale a falso y distinto de cero equivale a cierto.

1260 REMark ----------------------------------------
1270 REMark -- Definir Seudo-Contantes            --
1280 REMark ----------------------------------------
1290 LET No = 0          : REMark Valor para falso
1300 LET Si = 1          : REMark Valor para cierto
1310 LET Ascendente  = 0 : REMark Orden a montar
1320 LET Descendente = 1 : REMark Orden a montar
1330 :
1340 :
1350 REMark ----------------------------------------
1360 REMark -- Definir variables globales         --
1370 REMark ----------------------------------------
1380 LET m = 20         : REMark Nro maximo de rutinas a probar
1390 LET nrutina = 0    : REMark Algoritmo en prueba
1400 LET nropaso = 0    : REMark Paso en la prueba
1410 DIM nombres$(m,18) : REMark Nombres de algoritmos
1420 DIM tiempoi(m,3)   : REMark Guardar tiempos inicio
1430 DIM tiempof(m,3)   : REMark Guardar tiempos fin
1440 DIM nrocomp(m,3)   : REMark Numero de comparaciones
1450 DIM nromovi(m,3)   : REMark Numero de movimientos
1460 :
1470 DIM Abase(nroelem) : REMark Arreglo base aleatorio
1480 DIM Atemp(nroelem) : REMark Arreglo a ordenar

Solo queda ir llamando a los tres procesos que voy a utilizar, inicializar todo, llamar a la pruebas y presentar el resultado.

1510 REMark ----------------------------------------
1520 REMark -- Lanzar por procesos                --
1530 REMark ----------------------------------------
1540 Inicializar
1550 Probar
1560 INPUT "Finalizado",fin$
1570 Resultados
1580 STOP

El proceso de inicio crea un arreglo para los valores aleatorios y lo muestra en pantalla como referencia, para que veamos el origen.

1610 REMark ----------------------------------------
1620 REMark -- Inicializar                        --
1630 REMark ----------------------------------------
1640 DEFine PROCedure Inicializar
1650   Montar_arreglo Abase
1660   PRINT "----- Elementos a ordenar"
1670   Presentar_arreglo Abase
1680 END DEFine 

Paso al proceso que lanza las pruebas. En lenguajes que soporten punteros como el C o los orientados a objeto se puede crear un arreglo con los enlaces a las rutinas que definamos, no en SuperBASIC, por lo que empezamos un bucle indefinido, guiado por la variable nrutina en la que llevamos un contador de rutinas a probar, según el número seleccionamos el nombre del algoritmo o salimos del bucle. Luego hacemos tres pasadas por un bucle, la primera ordena el arreglo base aleatorio, la segunda con el mejor caso que es con el arreglo ya ordenado, y la tercera con el peor caso lo que invierte el arreglo completamente.

1710 REMark ----------------------------------------
1720 REMark -- Proceso de pruebas                 --
1730 REMark ----------------------------------------
1740 DEFine PROCedure Probar
1750   REPeat prueba_rutina
1760     Seleccion No
1770     IF nombres$(nrutina)="" THEN EXIT prueba_rutina
1780     PRINT "** Probando rutina ";nrutina;" ";nombres$(nrutina)
1790     :
1800     Copiar_arreglo Abase,Atemp
1810     FOR nropaso=0 TO 2
1820       IF nropaso <> 2 THEN 
1830         orden = Ascendente
1840       ELSE 
1850         orden = Descendente
1860       END IF 
1870       tiempoi(nrutina,nropaso)=DATE
1880       Seleccion Si,Atemp,orden
1890       tiempof(nrutina,nropaso)=DATE
1900       :
1910       Verifica_arreglo Atemp, orden
1920       :
1930       PRINT "-- ";nombres$(nrutina);
1940       SELect ON nropaso
1950         ON nropaso=0 : PRINT !" Aleatorio";
1960         ON nropaso=1 : PRINT !" Ordenado ";
1970         ON nropaso=2 : PRINT !" Inverso  ";
1980       END SELect 
1990       REMark PRINT !" (";DATE$;") "
2000       t=tiempof(nrutina,nropaso)-tiempoi(nrutina,nropaso)
2010       PRINT !"T: ";t;" seg";
2020       PRINT !"C: ";nrocomp(nrutina,nropaso);
2030       PRINT !"I: ";nromovi(nrutina,nropaso);
2040       PRINT
2050     END FOR nropaso
2060     :
2070     nrutina=nrutina+1
2080     IF nrutina > m THEN EXIT prueba_rutina
2090     :
2100   END REPeat prueba_rutina
2110 END DEFine 

Terminamos este grupo con la parte que presenta los resultados en la pantalla para poder compararlos todos entre sí. Para evitar líneas largas uso variables auxiliares con lo que mostrar.

2140 REMark ----------------------------------------
2150 REMark -- Presentar los resultados           --
2160 REMark ----------------------------------------
2170 DEFine PROCedure Resultados
2180   LOCal e1$,g1$,g2$
2190   :
2200   e1$=FILL$(" ",25)
2210   g1$=FILL$("-",24)
2220   g2$=FILL$("-",15)
2230   :
2240   CLS
2250   PRINT e1$;"+";g2$;"+";g2$;"+";g2$;"+"
2260   PRINT "       Con "; : Pnumero nroelem+1,3: PRINT " elementos";
2270   PRINT " |  Caso medio   |  Caso mejor   |   Caso peor   |"
2280   PRINT "+";g1$;"+";g2$;"+";g2$;"+";g2$;"+"
2290   FOR i=0 TO DIMN(nombres$)
2300     IF nombres$(i)="" THEN EXIT i
2310     t0=tiempof(i,0)-tiempoi(i,0)
2320     t1=tiempof(i,1)-tiempoi(i,1)
2330     t2=tiempof(i,2)-tiempoi(i,2)
2340     PRINT "| "; : Pnumero i,2
2350     PRINT " "; : PRINT nombres$(i);
2360     lon = 19-LEN(nombres$(i))
2370     IF lon > 0 THEN PRINT FILL$(" ",lon);
2380     PRINT " | "; : Pnumero t0,3
2390     PRINT " "; : Pnumero nrocomp(i,0),4
2400     PRINT " "; : Pnumero nromovi(i,0),4
2410     PRINT " | "; : Pnumero t1,3
2420     PRINT " "; : Pnumero nrocomp(i,1),4
2430     PRINT " "; : Pnumero nromovi(i,1),4
2440     PRINT " | "; : Pnumero t2,3
2450     PRINT " "; : Pnumero nrocomp(i,2),4
2460     PRINT " "; : Pnumero nromovi(i,2),4
2470     PRINT " |"
2480   END FOR i
2490   PRINT "+";g1$;"+";g2$;"+";g2$;"+";g2$;"+"
2500 END DEFine 

 
Luego tenemos rutinas auxiliares, la primera rellena un arreglo de un tamaño dado con valores aleatorios entre 10 y 99, de esta forma con un PRINT salen en columnas homogéneas.

2530 REMark ----------------------------------------
2540 REMark -- Rellena un arreglo con numeros     --
2550 REMark -- aleatorios de dos cifras           --
2560 REMark ----------------------------------------
2570 DEFine PROCedure Montar_arreglo(arreglo)
2580   LOCal i
2590   :
2600   FOR i=0 TO DIMN(arreglo)
2610     arreglo(i)=RND(10 TO 99)
2620   END FOR i
2630 END DEFine 

La segunda copia un arreglo sobre otro, es muy sencilla.

2660 REMark ----------------------------------------
2670 REMark -- Copiar un arreglo sobre otro       --
2680 REMark ----------------------------------------
2690 DEFine PROCedure Copiar_arreglo(origen,destino)
2700   LOCal i
2710   :
2720   IF DIMN(destino) < DIMN(origen) THEN 
2730     PRINT "ERROR copiando arreglo: Destino menor que origen"
2740     STOP
2750   END IF 
2760   :
2770   FOR i=0 TO DIMN(origen)
2780     destino(i)=origen(i)
2790   END FOR i
2800 END DEFine 

Luego otra para presentar por pantalla un arreglo, como todos los valores son de 2 cifras, mas el espacio intermedio, caben 25 valores por línea en modo 4.

2830 REMark ----------------------------------------
2840 REMark -- Presenta en pantalla un arreglo    --
2850 REMark ----------------------------------------
2860 DEFine PROCedure Presentar_arreglo(arreglo)
2870   LOCal i
2880   :
2890   FOR i=0 TO DIMN(arreglo)
2900     PRINT !arreglo(i);
2910   END FOR i
2920   PRINT
2930 END DEFine 

Para poder asegurarme de que las rutinas funciona bien, este proceso verifica que están bien ordenados los elementos del arreglo según el orden indicado.

2960 REMark ----------------------------------------
2970 REMark -- Ver si el arreglo esta ordenado    --
2980 REMark ----------------------------------------
2990 DEFine PROCedure Verifica_arreglo(arreglo, orden)
3000   LOCal i,hayerror
3010   :
3020   hayerror = No
3030   FOR i=0 TO DIMN(arreglo) - 1
3040     IF orden = Ascendente THEN 
3050       IF arreglo(i) > arreglo(i+1) THEN hayerror=Si
3060     ELSE 
3070       IF arreglo(i) < arreglo(i+1) THEN hayerror=Si
3080     END IF 
3090     IF hayerror THEN 
3100       PRINT "ERROR: Mal en orden";
3110       SELect ON orden
3120         = Ascendente  : PRINT !"ascendente";
3130         = Descendente : PRINT !"descendente";
3140       END SELect 
3150       PRINT !"Posicion ";i;"(";arreglo(i);")";
3160       PRINT !"Posicion ";i+1;"(";arreglo(i+1);")"
3170       Presentar_arreglo arreglo
3180       STOP
3190     END IF 
3200   END FOR i
3210 END DEFine   

Esta toma un número cualquiera y lo presenta relleno a ceros por la izquierda si es de menos de tres dígitos. Es sencillo ampliarla para que acepte como parámetro la longitud a rellenar.

3240 REMark ----------------------------------------
3250 REMark -- Presenta en pantalla un numero     --
3260 REMark ----------------------------------------
3270 DEFine PROCedure Pnumero(valor$,long)
3280   LOCal lon,aux$
3290   aux$=valor$
3300   IF aux$="" THEN aux$="0"
3310   lon = long - LEN(valor$)
3320   IF lon > 0 THEN aux$=FILL$(" ",lon) & aux$
3330   PRINT aux$;
3340 END DEFine 

Aquí terminan las rutinas de módulo base.

Módulo Selector

Este módulo contiene el procedimiento que llama al algoritmo en función del número, si no procesa monta la tabla de nombres de algoritmos, seguido por la línea que llama al algoritmo real. Hay que ir ampliándolo con los algoritmos que se desarrollen:

3500 REMark ----------------------------------------
3510 REMark -- ALGORITMOS DE ORDENACION           --
3520 REMark --   Modulo: Selector de algoritmos   --
3530 REMark --   Autor.: javu61, noviembre 2016   --
3540 REMark ----------------------------------------
3550 :
3560 :
3570 REMark ----------------------------------------
3580 REMark -- SELECCION DEL ALGORITMO            --
3590 REMark ----------------------------------------
3600 DEFine PROCedure Seleccion(procesar,arreglo,ordenacion)
3610   SELect ON nrutina
3620     ON nrutina=0
3630       nombres$(nrutina)="Burbuja"
3640       IF procesar THEN Burbuja arreglo,ordenacion,0,0
3650     ON nrutina=1
3660       nombres$(nrutina)="Burbuja Bidireccional"
3670       IF procesar THEN Sacudida arreglo,ordenacion,0,0
3680     :
3690     : REMark Aqui el resto de rutinas
3700     :
3710   END SELect 
3720 END DEFine 

Módulos de ordenación

Y por fin tenemos los métodos de ordenación, pongo la base de los dos primeros, la ordenación por burbuja y la ordenación por sacudida, solo para que el programa pueda ejecutarse y podemos ver cosas en pantalla. 

Modulo burbuja

4000 REMark ---------------------------------------------
4010 REMark -- ALGORITMOS DE ORDENACION                --
4020 REMark --   Modulo....: Burbuja                   --
4030 REMark --   Objetivo..: Ordena un arreglo por el  --
4040 REMark --               algoritmo de burbuja      --
4050 REMark --   Autor.....: javu61, 11/2016           --
4060 REMark --   Parametros:                           --
4070 REMark --     arreglo -> Arreglo a ordenar        --
4080 REMark --     sentido -> FALSO = Ascendente       --
4090 REMark --     primero -> primer elemento          --
4100 REMark --     ultimo  -> ultimo elemento          --
4110 REMark --                Si ultimo=0 -> Todos     --
4120 REMark ---------------------------------------------
4130 DEFine PROCedure Burbuja (arreglo,sentido,primero,ultimo)
4140   REMark Aqui va el codigo
4150 END DEFine 

Modulo sacudida

4500 REMark ---------------------------------------------
4510 REMark -- ALGORITMOS DE ORDENACION                --
4520 REMark --   Modulo....: Sacudida                  --
4530 REMark --   Objetivo..: Ordena un arreglo por el  --
4540 REMark --               algoritmo de burbuja      --
4550 REMark --               doble o sacudida          --
4560 REMark --   Autor.....: javu61, 11/2016           --
4570 REMark --   Parametros:                           --
4580 REMark --     arreglo -> Arreglo a ordenar        --
4590 REMark --     sentido -> FALSO = Ascendente       --
4600 REMark --     primero -> primer elemento          --
4610 REMark --     ultimo  -> ultimo elemento          --
4620 REMark --                Si ultimo=0 -> Todos     --
4630 REMark ---------------------------------------------
4640 DEFine PROCedure Sacudida (arreglo,sentido,primero,ultimo)
4650   REMark Aqui va el codigo
4660 END DEFine 

A partir de ahora solo presentaré los algoritmos que desarrolle en el QL, se añaden al final de todo, junto a código para manejarlos en el procedimiento anterior.

Podéis descargar el programa completo desde aquí, abrir los programas con un editor de textos (no el notepad que solo soporta textos con CR+LF) o cargarlo en un QL real o emulado.

Programación del Sinclair QL (VI): Procedimientos y funciones, paso de parámetros

Índice de entradas sobre programación del Sinclair QL

---

Parámetros por referencia y por valor

Tras tantos años acabo de descubrir un tema que no he visto reflejado en otros lugares, supongo que buscando un poco mas aparecerá, pero usando Q-Emulator con versión del SuperBASIC inglesa JS he probado este programa:

100 CLS
110 a=10
120 b(a)  : PRINT a
130 b a   : PRINT a
140 :
150 DEFine PROCedure b(c)
160   c=c+1
170 END DEFine

Si el paso de parámetros fuera siempre por valor, el resultado debían ser 10 y 10, pero el resultado es  10 y 11. Esto quiere decir que cuando llamamos a un procedimiento o función pasando los parámetros entre paréntesis pasan por valor, pero al pasarlos sin ellos lo hacen por referencia. Esto sería muy bueno si no fuera por que cuando llamamos a un procedimiento o función con mas de un parámetro, no podemos usar los paréntesis en la llamada pues da un error. Seguramente es uno de los famosos errores de la ROM del QL.

Parámetros opcionales

Otro tema que tampoco conocía y también acabo de descubrir es que se pueden usar parámetros opcionales de cierta manera, ya que mientras no los uses en tu programa no dará error:

100 CLS
110 x=5:y=5: b x   :PRINT x,y
120 x=5:y=5: b x,y :PRINT x,y
130 x=7:y=5: b x   :PRINT x,y
140 x=7:y=5: b x,y :PRINT x,y
150 :
160 DEFine PROCedure b(c,d)
170   c=c+1
180   IF c > 6 THEN d=d+1
190 END DEFine 

Esto presentará en pantalla por la línea 110 (6,5),  la 120 presenta (6,5), la 130 muestra (8,6), y al final un error de variable no definida al querer usar la línea 140.

Programación del Sinclair QL (V): Algoritmos de ordenación, clasifición y análisis

Índice de entradas sobre programación del Sinclair QL

---

Consideraciones sobre los algoritmos de ordenación

Los algoritmos de ordenación son vitales en informática, no solo para poder presentar los datos ordenados sino para poder optimizar las búsquedas en ellos, como demuestra que el volumen 3 de la serie de 7 de "El arte de programar ordenadores" de Donald Knuth se dedique a "Ordenación y búsqueda". Se considera que el primer algoritmo de ordenación fue desarrollado en 1951 por Betty Holberton, una de las 6 programadoras del ENIAC.

Los primeros ordenadores disponían de muy pocos recursos, por lo que los algoritmos iterativos que no requieren recursos podían usarse, pero si los datos eran numerosos había que recurrir a memoria externa como las cintas magnéticas y en esos casos se usaban la clasificación por mezcla de datos que eran mas efectivas. Cuando la potencia de calculo, la cantidad de memoria y los recursos externos como los discos duros fueron habituales, se crearon los algoritmos recursivos. Aparte de estos hay un cuarto grupo que no son estrictamente de ordenación, mas bien hacen lo contrario y en lugar de ordenar desordenan, que se emplean para estudiar los otros algoritmos.

Para elegir un algoritmo de ordenación hay que evaluar los varios puntos del algoritmo, que son los que utilizan más recursos del ordenador:

• Comparaciones: Para poder ordenar hay que comparar valores, el tiempo empleado en una comparación es proporcional a tamaño del dato, comparar enteros es rápido, comparar cadenas es mas lento. Evidentemente contra menos comparaciones mas rápido, y siempre el que menos necesite será de los más rápidos.
• Intercambios: Para ordenar hay que cambiar el orden de los registros, este tiempo puede ser proporcional al tamaño del dato si se mueve físicamente, o ser lineal si se cambian punteros nada mas. Los algoritmos iterativos mueven muchos datos intercambiándolos en memoria, los recursivos mueven una cantidad pequeña de datos también intercambiándolos en memoria, mientras que los de mezcla los mueven menos pero lo hacen a otras zonas de memoria ocupando mucha mas.
• Memoria auxiliar: Los algoritmos iterativos necesitan muy poco memoria auxiliar para su proceso, los recursivos requieren una cantidad proporcional a los datos que van a manejar, mientras que los de mezcla requieren una cantidad de memoria igual o mayor a la que ocupan los datos.
• Ubicación: Otro aspecto importante es donde de encuentran los datos, si estos están en memoria o en una unidad externa como un fichero en disco, los tiempos de acceso son mucho mas elevados, por lo que minimizando la cantidad de accesos se pueden lograr aumentos importantes de velocidad.

Clasificación según su estructura y análisis general

Como ingeniero informático no puedo dejar de mencionar los ordenes de tiempo y ocupación de memoria de los algoritmos, pero no voy a entrar mucho más, el análisis de algoritmos es un tema muy bonito y complejo por lo que si alguno lo desea puedo discutirlo en otras entradas.

• Algoritmos por intercambio: Se basan en ir intercambiando los elementos de la lista unos con otros ubicándolos o al menos acercándolos a su lugar correcto. Hay dos variantes generales:
  • Algoritmos por intercambio iterativos Son los que menos recursos de espacio necesitan, normalmente solo espacio para guardar uno de los datos a clasificar temporalmente, a cambio requieren mas pasadas entre los datos para ordenarlos. Son mas lentos, pero muy sencillos de programar, por lo que para cantidades pequeñas de datos son los preferidos, el mas conocido es el de Burbuja, que son 4 líneas de programa, en general es también el más lento pero si en un PC moderno ordenar por burbuja 100 datos cuesta menos de un segundo, ¿para que emplear tiempo en hacer otros algoritmos mas complejos? En general tardan un tiempo proporcional al cuadrado del número de registros a ordenar por tanto Velocidad Θ(n²), y requieren solo de un solo dato en memoria por tanto Ocupación Θ(1), por lo que en caso de poca memoria son los mas recomendables, por ejemplo si queremos ordenar 1000 bytes en una máquina con 1024 posiciones de memoria, con esos 24 bytes podemos programar uno de estos algoritmos.
  • Algoritmos por intercambio recursivos o por partición: Consiguen mucha mejor velocidad ya que ubican mas elementos en su lugar o muy cerca a la primera minimizando los intercambios. Van dividiendo la lista en sublistas a partir de un pivote, y las ordenan de forma que todos los elementos de la sublista anterior al pivote sean menores que él y los posteriores todos mayores, pasando luego a realizar el mismo proceso para cada una de las sublistas que se generan. Requieren mas memoria para la recursividad, pero reducen drásticamente el número de intercambios sobre los recursivos. El famoso QuickSort es el considerado mas rápido de los algoritmos de ordenación en casi todos los casos. Su tiempo en general es del orden de Velocidad Θ(n log n), igual que para los de mezcla, pero al ser recursivo Ocupación Θ(log n). Si dispones de memoria suficiente y de un lenguaje recursivo no dudes en usarlo, es sencillo de programar y el mas rápido casi siempre.
• Algoritmos por inserción: Variante de los de intercambio que buscan el lugar adecuado para un elemento y lo ubican en su lugar, desplazando el resto de elementos y minimizando así el número de intercambios. El mas conocido es el de Ordenación por Inserción. También los hay iterativos y recursivos, y su tiempo y ocupación en general es similar a los de intercambio, iterativos Velocidad Θ(n²) y recursivos Velocidad Θ(n log n), aunque al reducir el número de intercambios siempre son un poco mas rápidos. La ocupación en memoria es también similar, los iterativos Ocupación Θ(1) y los recursivos Ocupación Θ(log n).
• Algoritmos por selección: Estos algoritmos funcionan en dos pasos, primero utilizan estructuras auxiliares para clasificar los datos (usualmente creando un árbol), y luego lo recorren montando la lista ordenada. El mas usado es el de Ordenación por Montones (un montón es una forma de arbol binario que usa una lista) Al recorrer la lista una sola vez son rápidos y su velocidad es Velocidad Θ(n log n), pero requieren montar una estructura auxiliar por lo que necesitan tanta memoria como datos a ordena, y por tanto Ocupación Θ(n)
• Algoritmos de mezcla: Son los preferidos para ordenar cuando hay ubicaciones suficientes para ello, y siempre que se realiza en medios de almacenamiento auxiliares y no en memoria. Son mas rápidos pero requieren en general mucho espacio, habitualmente el mismo que ocupan los datos a ordenar si se realizan en memoria, pero se reduce mucho si es en disco. El mas popular entre estos es Merge Sort. Su tiempo varía mucho pero suelen estar en el orden de Velocidad Θ(n log n), y ocupan normalmente lo mismo que los datos a clasificar, por tanto Ocupación Θ(n) trabajando en memoria, pero pueden trabajar muy bien con memoria externa y en este caso Ocupación Θ(1). Apoyados en un medio de almacenamiento masivo son los mejores si estos ya están en memoria externa, así podemos ordenar en poco tiempo una gran cantidad de datos que no quepan en memoria.
• Algoritmos de distribución: Requieren un conocimiento previo de las claves a ordenar, ya que los van clasificando en grupos según un criterio, de forma similar a como se reparte el correo clasificándolo por códigos postales, luego por calles, por números de calle y finalmente por viviendas. El mas popular entre estos es el de Ordenación por Casilleros. Su tiempo es bueno ya que suelen ser Velocidad Θ(nk) , pero ocupan normalmente más que los datos a clasificar, por tanto Ocupación Θ(nk), con una k pequeña que puede llegar a ser 1 en algunos casos, pero con la limitación de ser muy dependientes del conocimiento de los datos a ordenar.
• Algoritmos concurrentes: En este grupo se incluyen algoritmos que se han diseñado específicamente para máquinas con varios procesadores (o varios núcleos) que trabajan a la vez de manera coordinada ordenando los datos. El mas usado es el Cube para ordenar los famosos "cubos" de análisis de datos, realmente arreglos multidimensionales.
• Algoritmos Híbridos: Es usual emplear varios algoritmos a la vez, por ejemplo Quicksort trabaja bien en listas grandes, pero mal cuando son ya pequeñas, por lo que se suele llamar a otro cuando las sublistas tienen ya pocos elementos. Este grupo de algoritmos hacen lo mismo, emplean dos métodos de ordenación complementarios para alcanzar el objetivo.
• Otros algoritmos: En este grupo se incluyen algoritmos especializados en un tipo de datos concreto, como grafos o qbits, o algoritmos muy imaginativos que son solo adecuados para el análisis de algoritmos ya que no son nada eficientes.
• Algoritmos de desordenación: Estos algoritmos son muy usados para producir resultados aleatorios en juegos. El mas antíguo es el Algoritmo del Sombrero. Estos algoritmos ordenan aleatoriamente los datos y repite el proceso hasta que por casualidad estén ordenados, por tanto no se puede usar para ordenar ya que su tiempo es del orden de los algoritmos intratables, con pocos datos puede ser del orden de Velocidad Θ(n!) aunque lo normal es que no acaben nunca. A cambio es muy usado para simular en un programa el barajar las cartas.

Algoritmos estables e inestables

Un registro puede contener claves primarias y secundarias de ordenación, por ejemplo cuando se ordena por Apellidos y Nombre una lista. Se considera un algoritmo estable cuando ordenan siempre los registros con claves primarias iguales en su orden por las secundarias, y se consideran inestables cuando no consiguen mantener el orden dentro de las secundarias. Esta inestabilidad se puede eliminar si unimos las claves primarias y secundarias en una clave única, al desaparecer las claves secundarias desaparece el problema.

Orden y desorden

Un punto importante es cuan desordenados están los datos inicialmente, esto nos puede ayudar a elegir uno u otro algoritmo, hay alguno especializado en listas casi ordenadas. Una forma de añadir un elemento a una lista es ubicarlo al final y llamar a la ordenación para que lo ponga en su lugar, por eso se distinguen tres casos que son los que usaré en las pruebas:

• Caso medio: Los datos están ordenados aleatoriamente, siendo este es el caso genérico que se usa para probar los algoritmos.
• Caso mejor: Los datos ya están ordenados, en este caso los últimos serán los primeros ya que la lenta Burbuja es el que mas rápido acaba normalmente. La comparación de este tiempo con el anterior nos proporciona una idea de la velocidad cuando los datos están casi ordenados.
• Caso peor: Los datos están en orden inverso, que es una buena prueba en la que los mejores algoritmos deben tardar mas o menos lo mismo que en el caso medio.

Las pruebas de los algoritmos de ordenación en memoria las voy a hacer de la siguiente forma para que sean comparables:

1. Genero un arreglo con el tamaño que se indique, y lo relleno de números enteros aleatorios, que pueden estar repetidos. Será el que use luego con todos los algoritmos y así no hay diferencias de partida.
2. Para cada algoritmo que deseo probar:
1. Caso medio: Copio el arreglo sobre uno temporal, y llamo al algoritmo para ordenar el arreglo temporal de menor a mayor. Cuento la cantidad de comparaciones, la cantidad de intercambios y el tiempo en segundos que tarda en total.
2. Caso mejor: Vuelvo a llamar al algoritmo con el arreglo temporal ya ordenado para que lo intente ordenar de menor a mayor, no debe mover ningún elemento del arreglo. Cuento la cantidad de comparaciones, la cantidad de intercambios y el tiempo en segundos que tarda en total
3. Caso peor: Vuelvo a llamar al algoritmo con el arreglo temporal ya ordenado para que lo intente ordenar de mayor a menor, lo que debe cambiar todos los elementos del arreglo. Cuento la cantidad de comparaciones, la cantidad de intercambios, y el tiempo en segundos que tarda en total.
3. Presento los resultados de todos los algoritmos.

Mas adelante lo volveré a hacer con los algoritmos de ordenación externos, que ordenen los datos almacenados en un fichero guardado en el microdriver, haciendo las modificaciones oportunas en el programa base.

Clasificación según su método de ordenación

Según el método que empleen para ordenar los datos hay una serie de familias de algoritmos. Los hay mas o menos rápidos, pero también se han desarrollado algoritmos impracticables, ya que el tiempo que tardan los hacen no abordables, y solo se han usado para el estudio de los algoritmos. No voy a desarrollar todos en superBASIC solo los mas habituales pues la lista es muy extensa, solo pongo aquí los algoritmos las más conocidos y ya son mas de 50:

Por Intercambio	Estos algoritmos son buenos trabajando sobre datos en memoria, trabajan intercambiando elementos de la lista a ordenar para ir acercándolos a su posición definitiva. Todos son variantes del denostado método de la Burbuja, y en general Inestables. Métodos iterativos Ordenación por Burbuja (Bubble sort) Ordenación por Sacudida o Burbuja Bidireccional (Cocktail shaker sort) Ordenación Par-Impar o de Pares y Nones (Odd–even sort) Ordenación de peine (Comb sort) Inestable Ordenación de vaivén o cremallera (Gnome sort o Stupid sort) Ordenación de Algunos Únicos (Several unique sort). Inestable. Algoritmo ineficiente ya que no mejora apenas la velocidad de la burbuja y por tanto solo es usado en análisis de algoritmos. Métodos recursivos Ordenación Rápida (Quicksort) Inestable Ordenación con Ayudante (Stooge sort o Trippel sort). Inestable e impracticable por su baja velocidad Ordenación Tonta (Sillysort). No mejora más que muy ligeramente la velocidad de la burbuja por lo que es un algoritmo ineficiente, solo usado en análisis de algoritmos.
Por Inserción	Se busca el lugar donde ubicar el elemento y se inserta en el, desplazando el resto de elementos si es necesario. Ordenación por Inserción (Insertion sort) Ordenación Shell (Shellsort) Por el nombre de su creador. Inestable Ordenación por Árbol Binario (Tree sort o Binary Tree sort) Ordenación por Árbol Biselado (Splaysort o Splay Tree sort) Algoritmo de la librería o de huecos (Library sort o Gapped insertion sort) Algoritmo de la Paciencia (Patience sorting), por un juego de cartas del solitario de ese nombre
Por Selección	Estos algoritmos utilizan estructuras auxiliares en memoria para aumentar la velocidad de proceso. Ordenación por montículos (Heapsort). Inestable, se considera poco eficiente por lo que no se recomienda su empleo. Ordenación por selección (Selection sort), inestable Ordenación de Dijkstra (Smoothsort) Por el nombre de su creador, muy bueno para listas casi ordenadas. Inestable. Ordenación por Árbol Cartesiano (Cartesian tree sort) Ordenación por torneo (Tournament sort) Ordenación por Ciclos (Cycle sort) Ordenación por Trozos (Strand sort)
Por Mezcla	Dividen los datos en grupos y van mezclándolos de forma ordenada. Su época dorada vino con las cintas magnéticas, y hoy son buenos para ordenación en disco. Ordenación por Mezcla (Merge sort), con su variante del Algoritmo de McCarthy (McCarthy's Algorithm) Ordenación Oscilante (Oscillating merge sort u Oscillating sort) Ordenación Polifásica (Polyphase merge sort o Polyphase sort), y su variante Ordenación por Cascada (Cascade merge sort o Cascade sort)
Por Distribución	Basados en la distribución de los elementos en varios casilleros, de forma similar a como se reparte el correo agrupándolo por códigos postales. Se diferencian principalmente en como se montan los casilleros. Algoritmos de distribución usables Ordenación por Casilleros o por Cajones (Bucket sort o Bin sort), con sus variantes del Algoritmo del Cartero (Postman sort), Ordenación por Huecos de Casillero (Pigeonhole sort), y Ordenación de las Barras o de la Bandera (American flag sort) Ordenación por Raíz o por Base (Radix sort), con variantes de Dígito Mas Significativo (MSD) y Dígito Menos Significativo (LSD) Ordenación por Ráfaga (Burstsort) Ordenación por Particiones (Proxmap sort) Ordenación por Destello (Flashsort) Ordenación por Contero o por Cuentas (Counting sort) Usa una técnica original Algoritmos impracticables Ordenación por Ábaco, por cuentas o por gravedad (Bead sort)
Algoritmos Concurrentes	Diseñados para el procesamiento en paralelo de los datos por varios procesadores simultáneamente. Algoritmos usables Ordenación de Batcher (Batcher odd–even mergesort). Por el nombre de su creador Ordenación en Parejas (Pairwise sorting network). Versión del Impar-Par para varios procesadors en paralelo. Ordenación del cubo (Cubesort). Bueno para arreglos multidimensionales Ordenación por Muestras (Samplesort) Algoritmos impracticables Ordenación por redes (Sorting network) y su variante Ordenación Bitónica (Bitonic sorter)
Algoritmos Híbridos	Es habitual usar varios algoritmos diferentes para acelerar el proceso, por ejemplo se suele usar mucho Quicksort que es bueno para listas grandes, las va reduciendo de tamaño cada vez hasta que son pequeñas, momento en que se usa otro algoritmo mas rápido con tamaños pequeños. Estos algoritmos hacen algo similar Ordenación por bloques (Block merge sort) Algoritmo de Tim (Timsort). Por el nombre del primero que lo programó Ordenación Introspectiva (Introsort or introspective sort) Ordenación por Propagación (Spreadsort) Ordenación sin Arrastre (UnShuffle Sort)
Otros Algoritmos	Algoritmos especializados Ordenación Topológica o de Grafos (Topological sort, Topological ordering, Topsort o Toposort) Algoritmos impracticables solo usados para análisis de algoritmos Ordenación de Tortitas, de Panqueques o de panecillos (Pancake sorting) Ordenación del Espagueti (Spaghetti sort) Ordenación del Diablo (EvilSort) Algoritmos para ordenadores cuánticos Ordenación Cuántica (Quantum sort)
Algoritmos desordenadores	Estos algoritmos desordenan las listas aleatoriamente. Por intercambio Falsa ordenación u Ordenación tonta (Bogosort, Slowsort, Stupid sort, Monkey sort). Impracticable para ordenar pero se usa para desordenar una lista ordenada Por inserción Algoritmo de Fisher-Yates, Ordenación Aleatoria o Algoritmo del Sombrero (Fisher–Yates shuffle, Random Sort o Hat Sort). Solo sirve para desordenar, por lo que es muy usado para barajar las cartas en los juegos. Existe una variante llamada Algoritmo de Sattollo (Sattolo's algorithm) por el nombre de su creador.