viernes, 29 de octubre de 2010

Optimizacón del algoritmo de ordenamiento SHELL

Allá por inicios de 1980 encontré el método de ordenamiento de Donald Shell que usó para su doctorado y me gustó sobremanera el algoritmo, luego de pensarlo varios días, apliqué lo que me habían enseñado en la Universidad de Piura, las derivadas para encontrar el valor óptimo (mínimo en este caso) y además el uso de logaritmos del colegio, pero tuve que aplicar un razonamiento para encontrar una ecuación nueva que luego terminó en una fórmula para optimizar el algoritmo de Shell.
Una breve descripción del algoritmo es que la comparación de los elementos se realiza a una distancia L, y luego en cada pasada de principio a fin esa distancia L se toma la mitad entera cada vez. Pues mi optimización se planteó que en vez de dividir entre 2 debería ser entre un valor D que este valor D debería dividirse entre dos cada siguiente vez para lo cual resultó que el valor inicial de
D = 2^INT[sqrt(0.25+2*LOG(L)/LOG(2))-0.5]. Para el caso de 1000 elementos D resulta en 8, entonces la distancia L es 125 (=1000/8), luego D pasa a ser 4 (la mitad) entonces L será 31 (=125/4) y para las siguientes pasadas D vale 2 y L tomará los valores 15, 7, 3 y 1.
Ahora bien, es posible que encuentre otro valor óptimo que en vez de ser ese valor D que se divida entre dos, pueda ser encontrar una serie de valores que responda mejor a determinadas cantidades a ordenar, supongamos que en vez de dividir entre 2 como originalmente planteó Donald Shell, posiblemente 2 sirva para cuando la distancia sea menor a 32, y sea 3 para distancias desde 33 hasta 1024, etc...
Al revisar las comparaciones entre los elementos, se me ocurrió preguntarme ¿Porqué tengo que comparar la misma pareja de elementos dos veces?, entonces puse unas distancias de comparación de manera que la misma pareja trate de compararse la menor cantidad de veces posible y he llegado a una serie que si es más veloz que el original de Shell (12-nov-2010) La fórmula para la primera distancia de compración ( o salto) es: L = 2^INT[LOG(N)/LOG(2)]-1, luego para cada siguiente vez es la parte entera de la mitad como usualmente es el algoritmo de Shell. He revisado en internet que esta fórmula ya había sido planteada por Hibbard o por Papernov-Stasevich en 1965; Pratt en 1971, así que me plantearé otras ecuaciones, para ver adonde llegaré.