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