martes, 15 de noviembre de 2016

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



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.

No hay comentarios:

Publicar un comentario