BotonMenu
BotonIndice

Visita : http://www.conoce3000.com
Paypal : https://www.paypal.me/conoce3000/1

PASCAL CON FREE PASCAL

PASCAL CON FREE PASCAL

PASCAL CON FREE PASCAL


8. ALGORITMOS DE ORDENACIÓN Y BUSQUEDA.
8.3. ORDENAMIENTO SHELL. (SHELL SORT)
8. ALGORITMOS DE ORDENACIÓN Y BUSQUEDA.
8.3. ORDENAMIENTO SHELL. (SHELL SORT)
8. ALGORITMOS DE ORDENACIÓN Y BUSQUEDA.
8.3. ORDENAMIENTO SHELL. (SHELL SORT)

SIGUIENTE

SIGUIENTE

SIGUIENTE


‒ Ordenamiento Shell.

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 con ello 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 lista casi 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 por inserció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

7 1
7 3 10 1 9 8 4


Se colocan los elementos ordenados por inserción

1 3 10 7 9 8 4


Desde el elemento 4. Elementos a ordenar: 3, 9

3 9
1 3 10 7 9 8 4


Se colocan los elementos ordenados por inserción

1 3 10 7 9 8 4


Desde el elemento 5. Elementos a ordenar: 10, 8

10 8
1 3 10 7 9 8 4


Se colocan los elementos ordenados por inserción

1 3 8 7 9 10 4


Desde el elemento 6. Elementos a ordenar: 1, 7, 4

1 7 4
1 3 10 7 9 8 4


Se colocan los elementos ordenados por inserción

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

Descargar
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

          for i:=intv to high(A) do // Desde el intervalo hasta el final
             Begin
                aux:=A[i];   
                j:=i-intv;   
                while ((j>=0) and (auxA<[j])) do 
                   Begin
                      A[j+intv]:=A[j]; 
                      j:=j-intv
                   End;
                A[j+intv]:=aux                   
             End;

           //nuevo intervalo

           intv:=intv div 2  
       End;
 End;
Código fuente 5: Primer algortimo de ordenación Shell.
Descargar

Tal como se puede observar el bucle while es el que controla la cantidad de intervalos a ordenar, y el resto viene a ser el mismo algoritmo de inserción adaptado para que se usen los intervalos que se van obteniendo. La variable j que es la clave de este algoritmo se va disminuyebdo de intervalo en intervalo (intv), en vez de hacerlo de 1 en 1 como en el algoritmo de inserción.

Este algoritmo también se puede adaptar para que no use la evaluación booleana en cortocircuito, a continuación el procedimiento correspondiente:


Descargar
Procedure Ordenar(A:LNaturales);    

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

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

          //algoritmo de inserción, por intervalos

          for i:=intv to high(A) do // Desde el intervalo hasta el final
             Begin
                j:=i-intv;    
                aux:=A[i];   
                IniLista:=false;
                while (not IniLista) and (aux<A[j]) do
                   Begin
                      A[j+intv]:=A[j];
                      if j>=intv then j:=j-intv else IniLista:=true
                   End;                 
                 if IniLista then A[j]:=aux  
                             else A[j+intv]:=aux                  
             End;

           //nuevo intervalo

           intv:=intv div 2 
       End;
 End;
Código fuente 6: Segundo algoritmo Shell, sin el uso de de evaluación booleana en cortocircuito.
Descargar

Este algoritmo de Ordenamiento Shell, tiene otras variantes, que se diferencian en la generación de la secuencia de intervalos. Originalmente la secuencia de intervalos es ir dividiendo con 2 los intervalos hasta llegar a 1, tomando como primer intervalo la longitud de la lista, pero cualquier secuencia de intervalos funcionará con este algoritmo siempre y cuando esta termine en 1. A continuación dos secuencias de intervalos que ofrecen un mejor rendimiento y de fácil implementación:

1era Secuencia de intervalos (Gonnet y Baeza-Yates): Esta secuencia de intervalos consiste en tomar la longitud de la lista multiplicarlo por 5 y después hacer una división entera con 11, para el siguiente intervalo, tomar el anterior multiplicarlo por 5 y hacer una división entera con 11, y así sucesivamente hasta llegar a 1. Sólo se debe tener en cuenta que cuando el intervalo es 2 este debe cambiarse siempre a 1.Por ejemplo si tenemos una lista de 100 elementos a ordenar, los intervalos serían. 45, 20, 9, 4, 1; pero en el caso de 150 elementos los intervalos serán: 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 intentáramos obtener el intervalo considerando el 2 obtendríamos 68, 30, 13, 5, 2, 0; y eso estaría 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, sólo cuando este aparezca. Ejemplo:


Descargar
Procedure Ordenar(A:LNaturales);    

Var i,j:longint;
    aux:qword;    
    intv:longword;    // intervalo   

 Begin     
     intv:=(length(A)*5) div 11;     //intervalo inicial     
     While intv>0 do   // Mientras intervalo > 0
       Begin          

          //algoritmo de inserción, por intervalos

          for i:=intv to high(A) do // Desde el intervalo hasta el final
             Begin
                j:=i;       
                aux:=A[i];                 
                while ((j>=intv) and (auxA<[j-intv])) do 
                   Begin
                      A[j]:=A[j-intv];     
                      j:=j-intv                 
                   End;
                 A[j]:=aux  
             End;
             
           // nuevo intervalo 

           intv:=(intv * 5) div 11 ;            
           if intv=2 then intv:=1
       End;
 End;
Código fuente 7: Algoritmo Shell, Gonnet y Baeza-Yates.
Descargar

2da Secuencia de intervalos (Steven Pigeon): Esta secuencia de intervalos está basado en la siguiente secuencia matemática: an=1+en-2, en donde, e es el número de Euler y n es cualquier número entero positivo mayor que 0, es decir n=1, 2 , 3, 4, 5, 6 ... ∞. A todos los valores de esta secuencia matemática 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 serían: 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 ecuación: 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 ecuación, 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 sólo elemento.


Descargar
Procedure OrdenarD(A:LNaturales);    
Var i,j:longint;
    aux:qword;    
    intv:longword;    // intervalo   
    n:longword;          
 Begin     
     
     //intervalo inicial
     intv:=0;
     if length(A)>1 then  // Debe ser mayor que 1 
       Begin
        n:=trunc(ln(length(A)-1)+2);
        intv:=trunc((1+exp(n-2))+0.5); 
       End; 
    
     While intv>0 do   // Mientras intervalo > 0
       Begin

          //algoritmo de inserción, por intervalos

          for i:=intv to high(A) do 
             Begin
                j:=i;        
                aux:=A[i];                   
                while ((j>=intv) and (auxA[j-intv])) do 
                   Begin
                      A[j]:=A[j-intv];     
                      j:=j-intv                 
                   End;
                 A[j]:=aux  //A[j+inc]:=aux
             End;
             
           //nuevo intervalo
           n-=1;
           if n>0 then intv:=trunc((1+exp(n-2))+0.5)
                       else intv:=0           
       End;
 End;
Código fuente 8: Algoritmo Shell, Steven Pigeon.
Descargar

En este algoritmo se puede observar que se comprueba que la longitud de la lista sea mayor que 1, en caso no lo sea la variable intv tendrá el valor 0, evitando ordenar la lista. Cada vez que se obtiene el nuevo intervalo se debe asegurar que n no llegue a valer 0, ya que si obtenemos un valor 0 para n, obtendremos un intervalo de 1, y si se sigue disminuyendo n obtendríamos un error de desbordamiento de punto flotante.

Los algoritmos mencionados anteriormente ordenan la listas de menor a mayor (ascendente), en caso quisiéramos hacerlo de mayor a menor (Descendente), sólo basta con cambiar la condición, aux<A[j-intv] por aux>A[j-intv].

El siguiente archivo comprimido: OrdenacionShell.zip,tiene 4 programas de ejemplo para los tipos de datos LNaturales, LEnteros, LReales y LPalabras de la unidad listas.




SIGUIENTE
SIGUIENTE
SIGUIENTE



 
‒ Comentarios y sugerencias.

Agradezco de antemano, todo comentario, sugerencia, y donativo (a través de Paypal me), que ayude a mejorar los contenidos educativos de Conoce 3000. Además, cualquier pregunta o duda que tengas lo puedes hacer por este medio. Pero, todo contenido que pueda resultar ofensivo, malicioso, racista, sexista, discriminatorio, obsceno, vulgar será eliminado.


Comments System WIDGET PACK






PORTADA |  INTERESANTE |  APUNTES |  LIBROS |  GALERIA


Creative Commons License


Todos los textos, imágenes y videos de Conoce3000 estan colocados bajo una licencia : Creative Commons Reconocimiento-NoComercial 3.0 Unported License.