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.
No hay comentarios:
Publicar un comentario