Ejemplos varios

















OTRO EJEMPLO

l método Shell de ordenación en Java para ordenar un array A de enteros es el siguiente:
public static void shell(int A[]){
   int salto, aux, i;
   boolean cambios;
   for(salto=A.length/2; salto!=0; salto/=2){
           cambios=true;
           while(cambios){ // Mientras se intercambie algún elemento
                       cambios=false;
                      for(i=salto; i< A.length; i++) // se da una pasada
                               if(A[i-salto]>A[i]){ // y si están desordenados
                                     aux=A[i]; // se reordenan
                                     A[i]=A[i-salto];
                                     A[i-salto]=aux;
                                     cambios=true; // y se marca como cambio.                               }
                        }
            }
}
Ejemplo de ejecución:


Con sólo 6 intercambios se ha ordenado el array, cuando por inserción se necesitaban muchos más. El rendimiento del método Shell de ordenación es bastante aceptable, aún para el caso de un número de elementos muy grande. Se ha comprobado que el tiempo de ejecución promedio es de O(n2/3) para la mayoría de las secuencias de salto.OTRO EJEMPLO
Este algoritmo de ordenación fue creado por Donald Shell, el algoritmo se denomina Shell en honor a su inventor. El algoritmo se parece al algoritmo de ordenación por inserción. En el algoritmo de inserción, cada elemento se compara con los elementos contiguos de su izquierda de uno en uno, pero con el algoritmo de Shell la comparación se hace con intervalos mayores a uno, logrando conello que la ordenación sea más rápida. 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 ordenación de la lista se hace con un intervalo de 1 el algoritmo se comporta como el algoritmo de inserción, pero con la ventaja de que al tener una listacasi ordenada, debido a los ordenamientos por intervalos anteriores, el ordenamiento se hará más rápido.
Veremos un ejemplo ordenando de menor a mayor (ascendentemente) la siguiente lista de números:
 
7, 3, 10, 1, 9, 8, 4
 
La lista tiene 7 elementos (de 0 a 6), con lo cual obtendremos un intervalo inicial de 3, división entera de 7 entre 2 (7 div 2). Desde el elemento 3 se ordena la lista porinserción, hacia la izquierda tomando los elementos de 3 en 3, y así hasta terminar de recorrer la lista.
 
1er recorrido: intervalo 3, resultado de la división entera de 7 entre 2.
 
Desde el elemento 3. Elementos a ordenar: 7, 1
 
Se colocan los elementos ordenados por inserción
 
 
 
7
 
 
1
 


7
3
10
1
9
8
4


1
3
10
7
9
8
4

 
Desde el elemento 4. Elementos a ordenar: 3, 9
 
Se colocan loselementos ordenados por inserción
 
 
 

3
 
 
9


1
3
10
7
9
8
4


1
3
10
7
9
8
4

 
Desde el elemento 5. Elementos a ordenar: 10, 8
 
Se colocan los elementos ordenados por inserción
 
 
 

 
10
 
 
8

1
3
10
7
9
8
4


1
3
8
7
9
10
4

 
Desde el elemento 6. Elementos a ordenar: 1, 7, 4
 
Se colocan los elementos ordenados por inserción
 
 
 
1
 
 
7
 

4
1
3
8
7
9
10
4


1
3
8
4
9
10
7 
2do recorrido: intervalo 1, resultado de la división entera de 3 entre 2.
 
La lista se ordena con un intervalo de 1, es decir desde el elemento 1 hasta el último elemento de la lista. En esta parte el algoritmo se comporta como en el algoritmo de inserción y la lista se ordena haciendo menos intercambios.
 
1
3
4
7
8
9
10
Los recorridos terminan cuando el intervalo sea mayor que 0. Ahoraveamos la primera implementación del algoritmo con el siguiente procedimiento:
 
 
Procedure Ordenar(A:LNaturales);

Var i,j:longint;
aux:qword;
intv:longword; //intervalo
Begin
intv:=length(A) div 2; //intervalo inicial

While intv>0 do // Mientras intervalo >0
Begin

//algoritmo de inserción, por intervalos...