azrael

El algoritmo es básicamente un QuickSort, al revés y usando busqueda binaria.

Proviene de la idea (fundamental) de que ordenar n elementos de un vector, es equivalente a hacer un “merge” de n vectores ordenados de un elemento (un vector ordenado de un elemento, es un elemento desordenado, lógico).

Por lo tanto lo que hallé es la forma de mezclar n vectores ordenados de forma óptima.

Como estaba convencido de que era una generalización de la búsqueda binaria (ya que es ordenación por comparación), no fué “tan” dificil:

Si quieres mezclar n vectores ordenados en un sólo vector ordenado, tan sólo has de coger el vector central, elegir su elemento central como pivote y situarlo dentro de los vectores que se encuentren en el centro de cada mitad. Pero para eso los elementos de los otros vectores tienen que estar ya situados respecto al resto, es recursivo.

Simplificando, cada elemento ha de buscarse únicamente en dos vectores, uno anterior y uno posterior, de forma recursiva y mediante búsqueda binaria y ¡voilá!

He subido a la forja de rediris  los algoritmos que funcionan de lo que llevo escrito .

No es aún, el algoritmo de ordenación definitivo, pero se le acerca.

De momento, el algoritmo más rápido  es poco más o menos igual de rápido que Quicksort, pero se debe exclusivamente a la implementación, pues en ambas implementaciones uso o(n log n) memoria auxiliar (un autentico despilfarro).

Está en camino una implementación con un uso de memoría constante (es decir, un algoritmo in-place), pero requiere bastante trabajo. De momento tengo los algoritmo escritos de forma recursiva, pero “conociendo” a los compiladores, más vale que los escriba de forma iterativa a mano.

Creo que la mejor versión será usando el algoritmo de merge que he llamado (muy original) oMerge (de óptimo).

Una vez que tenga ese algoritmo en su versión iterativa, prescindiré de algoritmos auxiliares, y escribiré un algoritmo con una sola recursión, como el de Quicksort. Pero creo que se puede ir más allá y eliminar esa recursión tambien, ya que al contrario que en quicksort, las llamadas recursivas del algoritmo principal no dependen de las anteriores.

Bueno, el que quiera ya puede probar las diferentes velocidades de los diferentes merges. Trastenado un poquito con el código fuente, tambien los tipos de ordenación, pero ya digo que de momento, no he escrito AÚN nada mucho más rápido que mergesort.

Feliz navidad y feliz año ;).

He modificado la imagen que en wikipedia ilustra Mergesort (de dominio público) para mostrar como funciona mi Optimal Comparison Sort.Recuerdo que para mezclar tres vectores, se usa el Merge3.Aprovecho para comentar que es el equivalente a un árbol balanceado.Las comparaciones en este caso son 10 para mi Optimal Comparison Sort , 14 para Mergesort y 15 para Quicksort eligiendo como pivote el elemento central. Espero un comportamiento proporcional para vectores aleatorios más grandes. (more…)

Sabemos la forma óptima de mezclar tres vectores ordenados, la de mezclar cuatro no será tan sencilla. (more…)

Me temo, que hoy, sin querer, he demostrado que el mejor algoritmo de ordenación no puede tener n-1 comparaciones para datos ordenados. La mala noticia es que las comparaciones para un algoritmo “óptimo” serán siempre superiores a n-1. La buena es que demostrando esto he encontrado un algoritmo de ordenación óptimo, tan óptimo como es posible. (more…)

Ordenar N elementos será igual que ordenar N vectores ordenados de un elemento.Esta operación es la fusión de vectores (merge), y conseguir el merge óptimo de N vectores ordenados sería equivalente al algoritmo de ordenación óptimo.De momento sabemos la forma de buscar un elemento en un vector, pero lo que necesitamos es el merge de dos vectores.Por lo tanto intentemos generalizar el algoritmo de búsqueda binaria, para dos vectores. El mejor algoritmo de merge conocido hasta el momento es muy simple, y dados dos vectores de a y b elementos respectivamente, siempre hace a+b-1 comparaciones.Evidentemente ese algoritmo no es el que buscamos, pero nos dará una cota de lo que buscamos que sea el peor caso para el merge de dos vectores.

Empecemos. Tenemos dos vectores, v1 y v2 

v1: |1|2|3|4|5|6|7|8|9| 

v2:|1|2|3|4|5|6|7|8|9|

Como queremos generalizar la búsqueda binaria, lo que es evidente es que la primera comparación a realizar será comparar los dos centros. 5<=5Tras ello, querremos situar uno de los dos centros comparados dentro del otro vector. La elección igual que con el redondeo en búsqueda binaria, no parece tener mucha importancia. Por las mismas razones que antes, elegiremos el primer centro de los dos.  Este elemento será nuestro pivote, para esta iteración del algoritmo.Por lo tanto:  

v1: |1|2|3|4|5|6|7|8|9| 

v2:|1|2|3|4|

5>2 

v1: |1|2|3|4|5|6|7|8|9| 

v2:|3|4|

5>3

v1: |1|2|3|4|5|6|7|8|9| 

v2:|4|

5>4

Por lo tanto, tenemos la posición del elemento central del primer vector en el segundo. Es decir, hemos separado los datos de la forma siguiente.

|1|2|3|4|   |5|    |6|7|8|9|

|1|2|3|4|            |5|6|7|8|9|

Podemos repetir la operación recursivamente, para los vectores que nos quedan a la izquierda de nuestro pivote por un lado, y para los vectores que nos quedan a la derecha de nuestro pivote por el otro. 

Ya tenemos un algoritmo de merge de dos vectores, óptimo en el número de comparaciones.

Como prueba de que no me equivoco, el numero de comparaciones siempre es igual o inferior al del merge clásico (a+b-1 para dos vectores de tamaño a y b).

Intuitivamente, creo que un algoritmo óptimo de ordenación por comparación, será una generalización de la búsqueda binaría.¿Porqué?Porque la búsqueda binaría es el algoritmo óptimo de búsqueda la posición de un elemento entre otros elementos ordenados. Esto se debe a que si tenemos N elementos ordenados, y como única operación la comparación, la operación que más información nos dará será siempre comparar con el elemento central, de esta forma a cada paso descartamos la mitad de los elementos a comparar.

Por ejemplo, si buscamos la posición el dato D en el vector V: 

i)                          V= |1|2|3|4|5|6|7|8|9 |                                        D=6 

Nuestra primera comparación será preferentemente 5<=6, ya que  5 es el elemento central del vector.  Así, descartamos las comparaciones con los elementos anteriores al 5 (y con el 5).

ii)                     V1= |6|7|8|9|      D=6 

Al quedar un número par de elementos, podemos elegir entre el redondeo a la izquierda o a al derecha, en terminos de valor medio, ambas elecciones resultan en la misma cantidad de comparaciones, sin embargo, en los computadores, las cachés hacen que en general los accesos secuenciales, de izquierda a derecha sean más rápidos. Aunque puede que eso no suponga una diferencia significativa, lo que es evidente es que no va a resultar peor.Por lo tanto la comparación será 7>6, con lo que descartamos todos los elementos superiores al 7, y el 7.

iii)                    V2= |6|                            D=6 

Comparamos 6<=6, por lo tanto tenemos el vector |6|6| ordenado.Lo juntamos con los “trozos” de vectores que hemos ido descartando, y nos da el resultado  |1|2|3|4|5|6|6|7|8|9 | 

(more…)

A parte de su interés practico evidente (ordenar datos rápido), un algoritmo “óptimo” supone un gran reto.

(more…)

Una pequeña discusión el la talk-page de sorting algoritms de Wikipedia, sobre un argumento que ya me dió Javifields en su día.

”

Comparison sort lower bound

I think a reference to Timsort (Python adaptive mergesort) should be done. Also, with adaptive comparison sorting algorithms in mind, I think there’s not yet a proof that log(n!) (n log n) is the best average order achievable. All that’s been proved is that worst case for any comparison sorting algorithm is n log n.

Re: Timsort. It’s certainly an interesting algorithm, particularly because it comes very close to the lower limit on the number of comparisons. The problem may be that there has been very litte scientific research into it. Tim Peters published some notes on it, but they consist mainly of benchmarks. Any article on it would be very brief, or fall foul of the “no original research” rule.

Re: O(n log n) bound. As far as I can see it’s basic information theory. Assuming n distinct keys, every comparison yields at most 1 bit of information, and that only in the case when you perform a comparison that splits the remaining permutation space exactly in two halves. So, assuming you have n! permutations with equal probability, lg(n!) comparisons on average is the absolute minimum. Grotendeels Onschadelijk 01:38, 19 August 2007 (UTC)

Re: I’m the one above. I know this basic information theory, Grotendeels, but if I’m right thats only a proof for the worst case, since by making a first sequential pass on the array you can use adaptive algorithms (even quicksort is adaptive!) to do less tan log(n!) comps. Also, an optimum alogithm, MUST do a first sequential pass on the array ( for O(n) case if ordered or inverted). Then the bound is O(n log n) ONLY if u can’t use the array pre-order. Maybe I’m wrong, but I think it’s possible to make an algorithm with an O(n log n)worst case bound, half that comparations on average, and O(n) best case. I have an idea to make it, but i’m unable to translate that to code without an enormous use of memory (at least n log(n)).Azrael60 23:28, 20 August 2007 (UTC)

Yes, it is possible to get algorithms with O(n log n) worst case. Mergesort is an example. Yes, it is possible to get O(n) for a limited number of cases. However, under the assumptions

• all keys are distinct, i.e. every comparison will give a>b or a<b, and
• the input is a random permutation, chosen uniformly from the set of all possible permutations,

it is impossible to even determine which order the input is in, in less that log₂(n!) comparisons on average.

The short argument is this: The Shannon entropy of a random permutation, distributed uniformly over all permutations of n elements is log₂(n!) bits. Since a comparison can give only two results, the maximum amount of information it can give is 1 bit. Therefore after k comparisons the remaining entropy of the permutation, given the results of those comparisons, is at least log₂(n!) - k on average. To perform the sort, we need complete information, that is, we need the remaining entropy to be 0. So we need at least k >= log₂(n!). As far as I can see I have made no worst case assumtions here, just the two assumptions noted above. Note, however, that this differs from the worst case argument, in that it does not allow rounding up to the nearest integer. For example, for n = 3, the lower bound for the worst case is 3, the lower bound for the average case as shown above is approximately 2.5849625007211561, while the highest lower bound for the average case is 8/3. Grotendeels Onschadelijk 01:18, 25 August 2007 (UTC)

I have added a slightly improved version of this argument under Comparison sort#Lower bound for the average number of comparisons. Grotendeels Onschadelijk 15:46, 25 August 2007 (UTC)”

A continuación el argumento en mayor profundidad (tendré que pensar en ello), en la página de cota mínima.

”

Lower bound for the average number of comparisons

The Shannon entropy of a random permutation, distributed uniformly over all permutations of n elements is log₂(n!) bits. Since a comparison can give only two results, the maximum amount of information it provides is 1 bit. Therefore after k comparisons the remaining entropy of the permutation, given the results of those comparisons, is at least log₂(n!) - k on average. To perform the sort, complete information is needed, so the remaining entropy must be 0. It follows that k must be at least log₂(n!).

Note that this differs from the worst case argument given above, in that it does not allow rounding up to the nearest integer. For example, for n = 3, the lower bound for the worst case is 3, the lower bound for the average case as shown above is approximately 2.58, while the highest lower bound for the average case is 8/3.

In the case that multiple items may have the same key, there is no obvious statistical interpretation for the term “average case”, so an argument like the above cannot be applied without making specific assumptions about the distribution of keys.”

Este sería el esquema de un algoritmo superadaptativo de ordenación por comparación, a modo de ejemplo. Sería muy rápido para datos presentando cualquier tipo de patrón, seguramente en el peor caso sea n log n, pero está lejos de ser óptimo, ni fácil de implementar. Creo firmemente que para ser óptimo debería de basarse en busqueda binaría en lugar de lineal y que el algoritmo resultante será recursivo y sencillo. Buscar “galopando” (exponencialmente, siguiendo los terminos de la sucesión de Fibonacci) también sería más rápido, pero más lento que una busqueda binaría.  Además pienso que  lo que más importa de un algoritmo es el número de comparaciones, el resto se lo dejo a la implementación.

algoritmo superAdaptativo (v)

ppio

si estaOrdenado(v) entonces

nada;

sinosi estaOrdenadoEnOrdenInverso entonces

invertir(t);

sino

superAdaptativo(maximos);

superAdaptativo(resto);

merge(resto,maximos);

finsi;

fin;

Hay que destacar, que el merge es un merge clasico y lineal, de coste a+b, y que al llamarse con “resto” los datos no serán elementos, sino vectores de elementos consecutivos (para no repetir comparaciones).

Un ejemplo de como debería de funcionar, con números aleatorios.

n=16  log2(16!)=44,25

SuperAdaptativo

4<=6>0<=0<=0<=5<=6>0<=7>0<=7<=8>2<=7<=8>0                                     comps=15

4>[0<=0<=0<=5]>0<=[0<=7]>[2<=7]>0 | 6<=6<=7<=8<=8                           comps=15+5+4=24

[0<=0<=0]<=[0<=0]<=2>0 | 4<=5<=7<=7                                                          comps=24+3+3=30

[0<=0<=0<=0<=0]<=0|2                                                                                         comps=30+1=31

[0<=0<=0<=0<=0<=0]<=2<=[4<=5<=7<=7]>[6<=6<=7<=8<=8]                 comps=31+1+1+1=34

[0<=0<=0<=0<=0<=0<=2<=4<=5]<=[6<=6]<=[7<=7]<=[7<=8<=8]           comps=32+4=36

SuperAdaptativo  Min-Max

4<=6>0<=0<=0<=5<=6>0<=7>0<=7<=8>2<=7<=8>0                                   comps=15

4>0<=0<=0<=2>0|[0<=0<=5]<=7<=7|6<=6<=7<=8<=8                                comps=15+11=26

0<=0|[0<=0]|4>2                                                                                                       comps=26+2=28

[0<=0]<=[0<=0]<=[2<=4]>[0<=0<=5<=7<=7]>[6<=6<=7<=8<=8]              comps=28+1+1+1+1=32

[0<=0<=0<=0]<=[0<=0]<=[2<=4]<=[5<=7<=7]>[6<=6<=7<=8<=8]            comps=32+4=36

[0<=0<=0<=0<=0<=0<=2<=4<=5]<=[6<=6]<=[7<=7]<=[7<=8<=8]             comps=36+3=39

MergesortAdaptativo

4<=6>0<=0<=0<=5<=6>0<=7>0<=7<=8>2<=7<=8>0                                    comps=15

0<=0<=0<=4<=5<=6<=6 | 0<=0<=7<=7<=8 | 0<=2<=7<=8                           comps=15+6+2+3=26

0<=0<=0<=0<=0<=4<=5<=6<=67<=7<=8| 0<=2<=7<=8                               comps=26+11=37

0<=0<=0<=0<=0<=0<=2<=4<=5<=6<=6<=7<=7<=7<=8<=8                        comps=37+15=52

Quicksort

4 6 0 0 0 5 6 0 7 0 7 8 2  7 8 0

4|0 0 0 0 0 2 0 | 6 5 6 7 7 8 7 8                                            comps=15

0 0 0 0 0 2 0 ||4|| 6 5 6 7 7 8 7 8                                          comps=15+6+7=28

||0|| 0 0 0 0 2 0 ||4|| 5 ||6||  6 7 7 8 7 8                             comps=28+5+5=38

||0 0|| 0 0 2 0 ||4 5 6 6 ||7 7 8 7 8                                        comps=38+3+4=45

||0 0 0|| 0 2 0 ||4 5 6 6 7 || 7 8 7 8                                       comps=45+2+3=50

||0 0 0 0|| 2 0 ||4 5 6 6 7 7|| 8 7 8                                        comps=50+1+2=53

0 0 0 0 0 2 4 5 6 6 7 7 7 8 8

Quicksort(no estable)

4 6 0 0 0 5 6 0 7 0 7 8 2  7 8 0

4|0 0 0 0 0 2 0 | 6 5 6 7 7 8 7 8                                             comps=15

0 0 0 0 0 2 0 ||4|| 6 5 6 7 7 8 7 8                                          comps=15+6+7=28

0 0 0 0 0 ||0 2 4|| 5 6 ||6|| 7 7 8 7 8                                    comps=28+4+1+4=37

0 0 0 0 ||0 0 2 4 5 6 6|| 7 7 ||7||8 8                                     comps=37+1+1=39

0 0 0 ||0 0 0 2 4 5 6 6 7 7  7 8 8||                                         comps=39+2=41

0 0 ||0 0 0 0 2 4 5 6 6 7 7  7 8 8||                                         comps=41+1=42

0 0 0 0 0 2 4 5 6 6 7 7 7 8 8

Las barras “|” separan “máximos” de “resto”, y los corchetes [] vectores ya comparados.
La zona entre dos barras “||” está ordenada.