“modified merge sort with exponential search intended for sorting data with pre-existing order” En la librería estándar de C de algún openBSD. Al menos parece que se comporta parecido.
Por otro lado, en un PDF del año de la pera (97), una versión de mergesort con 4 punteros gana a quicksort iterativo en el caso medio.
El algoritmo (que de momento seguiré llamando miMerge, hasta que descubra si tiene otro nombre), tiene bastante en común con el Bitonic Mergesort, aunque este no ordena de forma tan “inteligente”. El Bitonic Mergesort, por otro lado tiene la ventaja de requerir un hardware más simple, y por lo tanto se usa para aprovechar su gran paralelización en GPU’s.
¿Y cual era el problema de miMerge? Al parecer efectivamente es asimptoticamente óptimo en el caso medio. También es optimo para vectores ya ordenados, pero heredá el gran fallo del merge sort original: utiliza o(n) memoría.
El bitonic mergesort sin embargo no tiene ese problema, pero a costa de pasar a un tiempo medio n log^2 n, que no es óptimo, y también será este su coste en el caso de vectores ordenados.
Así pues, parece que el gran problema de este algoritmo sigue estando en encontrar una función merge óptima, que sea in place. Puede que eso sea demasiado para mi… ya veremos.
Las dos operaciones extra que me salen deben de ser las inversiones, pero me extraña, porque estaba convencido de que en el peor caso miMerge haría exactamente las mismas operaciones que mergesort. Creo que no tienen porque hacerse inversiones, si no sólo tener en cuenta que ese trozo de vector esta ordenado en orden inverso.
Este algoritmo iterativo está inspirado en Merge Sort de Von Neuman.
La idea básica es que Merge Sort no aprovecha el orden intrínseco de cualquier vector desordenado (como mínimo los elementos estarán ordenados de dos en dos).
Los objetivos (que no sé si he alcanzado, porque son ideales), són:
-Un algoritmo que aproveche al máximo el orden existente en un vector dado.
-Ordenación en N para un vector ya ordenado, ordenación en 2N para un vector ordenado en orden inverso.
-Ordenación en n log n para el peor caso.
-Numero de comparaciones mínimo, exactamente igual al de mergesort.
Como se ve, estos dos últimos son los más difíciles (de hecho supongo que el número de comparaciones de mergesort no es mínimo).
Como aún no he visto ningún algoritmo de este estilo propongo el mío.
Se buscan los (i-a+1) primeros elementos ordenados (en orden creciente o inverso), luego los siguientes (i-a+1) elementos ordenados y se mezclan los dos vectores ordenados para formar un vector resultado, ordenado en orden creciente, se continua de la misma forma, mezclando los siguientes (i-a+1) elementos ordenados con el vector resultado precedente.
a será por lo tanto el indice del primer elemento de un trozo de vector ordenado, e i el indice del último elemento de ese mismo trozo de vector ordenado
algoritmo miMerge (v: ES vector) es
orden:bool;
a,i:tpIndice;
ppio
i:=1;
a:=i;
orden:=directo;
mQ no i>=DIM(v)
si v[i]<v[i+1]
si orden = directo
sigue;
si_no –orden =inverso
mergeInvirtiendo(a,i);
orden:=directo;
a:=i+1;
fSi;
si_no — v[i]>=v[i+1]
si orden = directo
merge(a,i);
orden:=inverso;
a:=i+1;
si_no –orden =inverso
sigue;
fSi;
fSi;
i:=i+1;
fMQ;
fin;
P.D.: Sí el algoritmo está mal, o su coste en el peor caso es N!, que nadie me tiré una piedra a la cabeza, con explicarme lo que está mal e intentar optimizarlo valdría.
P.D.2:Después del Paso De Ecuador escribo mergeInvirtiendo y merge :P. Adelanto que mergeInvirtiendo, invierte y luego mezcla.
Yo soy de la creencia de que tiene que haber un algoritmo de ordenación mejor que Quicksort, un algoritmo que haga el numero imprescindible de comparaciones y ni una más.
Pero mientras no se me ocurra otro algoritmo, lo mejor que hay es Quicksort :P.
Una practica común es añadirle pequeñas optimizaciones a Quicksort, como que al trabajar con pocos elementos se use inserción o que si se detecta un caso malo se cambie a otro algoritmo (heapsort en el caso de introsort).
Otra posibilidad sería recorrer primero el vector de elementos, para comprobar si esta o no ordenado (en orden directo o inverso). De esta forma si no lo esta tendremos ya un “buen” pivote (el primer elemento no ordenado).
Esto añadirá posiblemente muchas comparaciones (máximo O(n)), así que no se si será practico, aunque el mejor caso sería O(n) (para vectores ordenados).
¿Y un algoritmo de ordenación que busque trozos ordenados (de forma directa o inversa) en el vector y luego los junte (a la mergesort)? Su peor caso sería n/2 vectores ordenados, de 2 elementos, a juntar. El mejor n-1 comparaciones para vectores ordenados.
Aprovechare la última practica de metodología de la programación para probar la eficiencia de versiones de todos estos algoritmos.
Desde el punto de vista de un programador de videojuegos, hacia aquí debería de ir un futuro lenguaje de programación. Miraros la presentación porque es muy sencillita e interesante. Curioso que en Haskell ordenar sea equivalente a Quicksort :p.
Explicándolo de forma sencilla; ordenar n datos es lo mismo que poner el dato mínimo en la posición inferior, el máximo en la posición superior y repetir el algoritmo para n-2 datos.
O lo que es lo mismo 1/2(n^2-n) = 1 + 2(n-1) + 1/2((n-2)^2-(n-2).
Tambien podría hacerse 1/2(n^2-n)= n-1 + 1/2((n-1)^2-(n-1)), que de hecho es el algoritmo de selección.
Así que he reinventado la rueda :P. El algoritmo es un cocktail sort por selección recursivo.
P.D.: ¿Pero a que queda bonito simétrico y recursivo?
Por fin he sacado un algoritmo en claro.
Creo que el tiempo es siempre 1/2(n^2-n) y fuerza mucho con la recursividad.
No es n log n, pero me ha parecido bonito. No sé si funcionará porque no consigo probarlo.
Si sabéis si hay alguno parecido avisadme.
—————————————————————-
procedure ordenar (T: in out tpLista)is
—————————————————————-
————————————————————-
procedure OrdenarIzda (T: in out Tplista)is
————————————————————-
aux:tpDato;
begin
if Numdatos(T)>1 then
if T(T’First)>T(T’Last) then–intercambia
Aux:=T(T’First);
T(T’First):=T(T’Last);
T(T´Last):=Aux;
end if;
if T’Last-T’First/=1 then
OrdenarIzda(T(T’First..T’Last-1));
end if;
end if;
end Ordenarizda;
————————————————————-
————————————————————-
procedure OrdenarDcha (T: in out Tplista)is
————————————————————-
aux:tpDato;
begin
if Numdatos(T)>1 then
if T(T’First)>T(T’Last) then–intercambia
Aux:=T(T’First);
T(T’First):=T(T’Last);
T(T´Last):=Aux;
end if;
if T’Last-T’First/=1 then
OrdenarDcha(T(T’First+1..T’Last));
end if;
end if;
end OrdenarDcha;
————————————————————-
aux:tpDato;
begin
if Numdatos(T)>1 then
if T(T’First)>T(T’Last) then–intercambia
Aux:=T(T’First);
T(T’First):=T(T’Last);
T(T´Last):=Aux;
end if;
if T’Last-T’First/=1 then
OrdenarIzda(T(T’First..T’Last-1));
Ordenar(T(T’First+1..T’Last-1));
OrdenarDcha(T(T’First+1..T’Last));
end if;
end if;
end ordenar;
—————————————————————
Vaya burradas he escrito estos días. Me salva que no estoy durmiendo lo suficiente.
Un árbol binario con n nodos (y no hojas) tiene una altura log n.
Por lo tanto el maravilloso método de ordenación al que le estaba dando vueltas no tendrá nunca complejidad n log n.
Tán sólo será un algoritmo de ordenación por burbuja optimizado, supongo que de coste medio 1/2(n^2-1) . El mejor caso sería como en ordenación por burbuja n. De todas formas si me da tiempo acabaré el algoritmo.
Sigo sin ver como es posible que con menos comparaciones se puedan ordenar n elementos, empiezo a pensar seriamente si no debería de haberme metido a letras.
EDIT: Sigo dándole vueltas a estas tonterías que parece, me superan. No sé porque coño estaba hablando de árboles binarios cuando estaba hablando de combinaciones. Hasta hace un momento no me he dado cuenta de que no es lo mismo.
Definitivamente tengo que dormir más.(Que pesimista me ha salido el post.)
Aún puede ser que la idea que me rondaba la cabeza sea de alguna utilidad: una especie de Quicksort invertido.
Tirado en la cama este mediodía, me ha parecido dar con la “chispa” del n log n.
El árbol binario de n hojas tiene 1/2(n^2-n) nodos y una altura log n.
El árbol binario de n hojas tiene n-1 nodos y una altura log n-1. (No estaba pensando en árboles binarios sino en combinaciones.)
Por lo tanto un algoritmo de ordenación tendría complejidad log n si hiciera en cada iteración las comparaciones correspondientes a todo un nivel del árbol. Pero el numero de comparaciones en cada nivel del árbol depende de n.
Podríamos pensar que entonces la complejidad será de orden n log n… pero hay algo que no me cuadra. No tengo la cabeza para pensar, pero ¿la complejidad no sería 1/2(n^2-n) log n ? xD