Este algoritmo de ordenacin fue creado porDonald Shell, el algoritmo se
denomina Shell en honor a su inventor. El algoritmo se parece al algoritmo
de ordenacin por insercin. Generalmente se toma como intervalo inicial n
div 2, siendo n la cantidad de elementos de la lista a ordenar, luego se
reduce los intervalos a la mitad hasta que el intervalo llegue a ser uno.
Cuando la ordenacin de la lista se hace con un intervalo de 1 el algoritmo
se comporta como el algoritmo de insercin, pero con la ventaja de que al
tener una lista casi ordenada, debido a los ordenamientos por intervalos
anteriores, el ordenamiento se har ms rpido.
os (de 0 a 6), con lo cual obtendremos un intervalo inicial de 3, divisin
entera de 7 entre 2 (7 div 2). Desde el elemento 3 se ordena la lista por
insercin, hacia la izquierda tomando los elementos de 3 en 3, y as hasta
terminar de recorrer la lista.
En el algoritmo de insercin, cada elemento se
compara con los elementos contiguos de su
izquierda de uno en uno, pero con el algoritmo de
Shell la comparacin se hace con intervalos
mayores a uno, logrando con ello que la
ordenacin sea ms rpida.
Caracteristicas
Se trata de un algoritmo de ordenacin interna.
Al igual que cualquier otro de ordenacin interna (los datos estn en
memoria principal) podra utilizarse para ordenacin externa (en memoria
secundaria) siempre y cuando se disponga de acceso aleatorio, pero el
algoritmo no fue ideado para eso.
Se basa en comparaciones e intercambios.
Necesita que el tiempo de acceso a cualquier dato sea constante (es decir,
fue ideado para trabajar con arrays, arrays de referencias o punteros,
etc...). Ojo a otras estructuras, como listas enlazadas, etc... ya que en ese
caso, el tiempo de acceso a un elemento no es constante, depende de la
posicin del elemento.
No es estable: dados dos elementos que al compararlos sean "iguales" -es
decir, que pueden ir indistintamente en la misma posicin, no mantienen
necesariamente el orden relativo inicial entre ellos.
El estudio de su complejidad no es trivial, sino todo lo contrario. La
implementacin original de Shell tiene una complejidad en el peor caso de
O(n2), aunque en un caso promedio o en casos tpicos comprobados
empricamente, los resultados son mucho mejores que con la burbuja,
seleccin directa o insercin directa, cuya complejidad en el peor caso
tambin es del orden de O(n2).
Sin embargo, optimizaciones posteriores han logrado reducir esa cota...
Por ejemplo, con la optimizacin de Robert Sedgewick(external link) se
llega a O(n4/3), y con la propuesta por Vaughan Pratt(external link) se
Algoritmo de Ordenacion Shell
Variables: Entero i, z, aux, int, valores (20, 40,16,12,8)
Inicio
intv=5/2
Mientras (intv > 0)
Para i = intv hasta i < 5 Paso 1
aux = valores (i)
z = i-intv
Mientras ((z>=0)&&(aux < valores(z)
valores( z + intv)=valores(z)
z = z-intv
Fin_mientras
valores(z+intv) = aux
Fin_Para
intv = intv/2
Fin_Mientras
Fin
1era Secuencia de intervalos (Gonnet y Baeza-Yates): Esta secuencia de intervalos
consiste en tomar la longitud de la lista multiplicarlo por 5 y despus hacer una divisin
entera con 11, para el siguiente intervalo, tomar el anterior multiplicarlo por 5 y hacer
una divisin entera con 11, y as sucesivamente hasta llegar a 1. Slo se debe tener en
cuenta que cuando el intervalo es 2 este debe cambiarse siempre a [Link] ejemplo si
tenemos una lista de 100 elementos a ordenar, los intervalos seran. 45, 20, 9, 4, 1;
pero en el caso de 150 elementos los intervalos sern: 68, 30, 13, 5, 1. Como puede
observar del 5 se salto al 1, ignorando el 2 que es resultado de (5*5) div 11. Esto es
por lo siguiente: Si intentramos obtener el intervalo considerando el 2 obtendramos
68, 30, 13, 5, 2, 0; y eso estara muy mal porque la secuencia de intervalos no termina
en 1 sino en cero, es por eso que se debe cambiar el 2 por el 1, slo cuando este
aparezca.
2da Secuencia de intervalos (Steven Pigeon): Esta secuencia de intervalos est
basado en la siguiente secuencia matemtica: an=1+en-2, en donde, e es el nmero
de Euler y n es cualquier nmero entero positivo mayor que 0, es decir n=1, 2 , 3, 4, 5,
6 ... . A todos los valores de esta secuencia matemtica se debe redondear antes de
obtener la parte entera, que se usar como intervalo. Para una lista de 150 elementos
los intervalos con dos cifras decimales sin redondear seran: 1.36, 2.00, 3.71, 8.38,
21.08, 55.59, 49.41, redondeando obtendremos: 1, 2, 4, 8, 21, 56, 149. El
ordenamiento shell ordena la lista usando los intervalos desde el mayor hasta 1, por lo
que se necesita obtener el intervalo an que sea menor que la longitud de la lista, para
ello despejamos n de la siguiente ecuacin: a=1+en-2, en donde a es la longitud de la
lista, con lo que obtenemos la siguiente ecuacion: n=ln(a-1)+2, (ln=logaritmo
neperiano) el valor devuelto por la ecuacin, debe ser truncado para obtener un valor
entero que nos permite obtener el intervalo an menor a la longitud de la lista. Hay que
tener presente que si la lista tiene longitud de 1 entonces al obtener el valor de n, se
intentar obtener el ln(0), esto producir un error, que se puede evitar con una
estructura de control if-then-else al inicio del procedimiento. En donde se evita
ordenar la listas cuando este es de un slo elemento.
Algoritmo Normal
Algoritmo Optimizado
Conclusiones:
Este es un algoritmo eficaz, relativamente eficiente en la mayora de los
casos, fcil de implementar, no consume memoria extra dinmicamente y se
comporta bastante bien para unos datos de entrada de mediano tamao.
Por ltimo, todo esto est muy bien... pero yo he utilizado este algoritmo para
ordenar enteros Se puede utilizar para ordenar Objetos u otro tipo de datos?
Pues s... sin ningn problema, pero hay que adaptarlo un poco. Primero,
necesitamos tener un criterio claro de ordenacin, y que algn mtodo nos
permita saber dados dos objetos cualesquiera si estn en orden o no. Mira
cmo lo hicimos con en el apartado correspondiente del algoritmo de la
burbuja. Lo mismo se puede aplicar al algoritmo de Shell.
