viernes, 15 de enero de 2010


Shell short
//Shell sort original con cuatro bucles
//Correcto, aunque no es la implementación más común
void ShellSort(int[] A)
{
//el primer salto o gap (representado por la variable k)
//es la mitad de la longitud del array
int k=A.Length/2;
//este primer bucle nos mantendrá dentro del algoritmo
//mientras el salto sea mayor o igual que 1. Antes de
//cada iteración dividimos el salto o gap (k) entre 2
while (k>=1)
{
//este segundo bucle cuenta los subarrays que nos
//salen para cada valor de salto k.
for (int subarray = 0; subarray < k; subarray++)
{
//para cada subarray recorremos sus elementos
//con este otro bucle for, desde el segundo
//hasta el último. Este bucle es igual que el del
//algoritmo de inserción directa, pero adaptado
//para un salto k
for (int i = k+subarray; i < A.Length; i += k)
{
int v = A[i]; //tomamos el elemento i-ésimo
int j = i - k; //apuntamos al anterior en el subarray
//Con este bucle desplazamos elementos en el subarray
//hasta encontrar la posición que le corresponde
//al elemento i-ésimo que tenemos guardado en v
//Es como el bucle interior de la inserción directa
//pero adaptado para moverse por un subarray con
//con salto k
while (j >= 0 && A[j] > v)
{
A[j + k] = A[j];
j-=k;
}
A[j + k] = v;
} //fin for
} //fin for
//obtenemos un nuevo salto
k /= 2;
} //fin while
} //ShellSort

No hay comentarios:

Publicar un comentario