jueves, 17 de noviembre de 2016

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



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 las todos las usen, así simplifico su código y hago que la comparación es 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.

No hay comentarios:

Publicar un comentario