Programación del Sinclair QL (XII): Ordenación por intercambio recursivo, Quicksort de tres vias

Índice de entradas sobre programación del Sinclair QL

---

Ordenar listas con elementos repetidos

Quicksort produce dos sublistas con los valores menores y mayores al pivote elegido, pero si la lista tiene elementos repetidos, podemos usar una variante del algoritmo denominada de 3 vías, que genera 3 sublistas:

• Sublista izquierda: elementos menores al pivote
• Sublista central: elementos iguales al pivote (de al menos hay un elemento)
• Sublista derecha: elementos mayores al pivote

Como la sublista central está ordenada y correctamente ubicada ya no entra en el juego, y se llama a la rutina de forma recursiva con las sublistas izquierda y derecha. Esta técnica no ralentiza la rutina apenas, por lo que es posible usarla aunque no tenga elementos repetidos. También da origen a una variante en la que se usan dos pivotes para generar tres sublistas, pero no la presentaré pues no aporta demasiado.

ALGORITMO Qsort3 (arreglo, primero, ultimo)

    SI (ultimo <= primero) ENTONCES
      RETurn
    FIN SI 
    
    izquierda ← primero
    derecha ← ultimo
    pivote ← primero
    pos ← primero+1

    MIENTRAS (pos <= derecha) 
      cmp ← COMPARA_ELEMENTOS(pos, pivote)
      SI cmp = -1 ENTONCES
          SWAP arreglo(izquierda),arreglo(pos)
          izquierda←izquierda+1
          pivote←pivote+1
          pos←pos+1
      SI cmp =  0 ENTONCES
          pos←pos+1
      SI cmp = +1 ENTONCES
          INTERCAMBIA_ELEMENTOS(pos, derecha)
          derecha←derecha-1
      FIN SI 
    FIN MIENTRAS

    Qsort3 arreglo, primero, izquierda-1
    Qsort3 arreglo, derecha+1, ultimo

Esto lo convierto a superBASIC con esta rutina con dos mejoras, para optimizar si la lista es de dos elementos los comparo e intercambio directamente si es necesario, así acelero un poco el algoritmo, y solo hago llamadas recursivas si hay elementos en las sublistas, para ahorrar llamadas no necesarias. La segunda optimización es que en lugar de usar el primer elemento como pivote, uso el central y lo pongo como primero antes de empezar, así en caso de listas casi ordenadas o en orden inverso funciona mejor el algoritmo.

17140 DEFine PROCedure Rapida_3vias (arreglo,sentido,primero,ultimo)
17150   IF ultimo=0 THEN ultimo=DIMN(arreglo)
17160   Qsort3 arreglo, sentido, primero, ultimo
17170 END DEFine 
17180 :
17190 :
17200 DEFine PROCedure Qsort3(arreglo, sentido, primero, ultimo)
17210   LOCal izquierda,derecha,pivote,pos,repetir,cmp
17220   :
17230   IF (primero+1 = ultimo) THEN 
17240     IF COMPARA(arreglo(primero),arreglo(ultimo),sentido) > 0 THEN 
17250       SWAP arreglo(primero),arreglo(ultimo)
17260     END IF 
17270   ELSE 
17280     izquierda = primero
17290     derecha = ultimo
17300     pivote = INT((primero+ultimo)/2)
17310     SWAP arreglo(primero),arreglo(pivote)
17320     pivote = primero
17330     pos = primero+1
17340     :
17350     REPeat repetir
17360       IF (pos > derecha) THEN EXIT repetir
17370       cmp = COMPARA(arreglo(pos),arreglo(pivote),sentido)
17380       SELect ON cmp
17390         =-1
17400           SWAP arreglo(izquierda),arreglo(pos)
17410           izquierda=izquierda+1
17420           pivote=pivote+1
17430           pos=pos+1
17440         = 0
17450           pos=pos+1
17460         =+1
17470           SWAP arreglo(derecha),arreglo(pos)
17480           derecha=derecha-1
17490       END SELect 
17500     END REPeat repetir
17510     :
17520     REMark Sublista 1: arreglo[primero..izquierda-1]
17530     REMark Sublista 2: arreglo[izquierda..derecha] = pivote
17540     REMark Sublista 3: arreglo[derecha+1..ultimo]
17550     IF primero < izquierda-1 THEN 
17560       Qsort3 arreglo, sentido, primero, izquierda-1
17570     END IF 
17580     IF ultimo > derecha+1 THEN 
17590       Qsort3 arreglo, sentido, derecha+1, ultimo
17600     END IF 
17610   END IF 
17620 END DEFine

En todas las pruebas que he efectuado el resultado final es que el mejor en tiempos siempre es el algoritmo mas sencillo, que es el segundo de los tres presentados, y usar el elemento central es ligeramente mejor que usar un elemento aleatorio como pivote. Si la lista tiene muchos repetidos, la variante de 3 vías es mejor que las otras, pero si no hay demasiada repetición al ser mas complejo tarda siempre un poco mas. En el caso mejor, el algoritmo con pivote variable genera muchas sublistas de dos elementos, pero al introducir el que esos dos elementos se comparen directamente se acelera el proceso y no se produce ningún intercambio, pero sigue siendo un algoritmo malo en caso de lista casi ordenada o en orden inverso.



He vuelto a modificar la rutina de comparación, ahora paso al enfoque clásico en que se comparan dos valores y se retorna 0 si son iguales, 1 si el primero es mayor y -1 si es menor. Mantengo el uso del parámetro del sentido para mantener al máximo los algoritmos originales, aunque ya no hace falta con este nuevo enfoque, lo cambiaré en breve:

3560 DEFine FuNction COMPARA(a,b,sentido)
3570   :: nrocomp(nrutina,nropaso)=nrocomp(nrutina,nropaso)+3
3580   IF sentido=0 THEN 
3590     IF a < b THEN RETurn -1
3600     IF a = b THEN RETurn  0
3610     IF a > b THEN RETurn +1
3620   ELSE 
3630     IF a > b THEN RETurn -1
3640     IF a = b THEN RETurn  0
3650     IF a < b THEN RETurn +1
3660   END IF 
3670 END DEFine

Y aquí os dejo los ficheros modificados, como siempre solo hay que cargar y ejecutar om_carga para que monte todo el sistema y lance los algoritmos.