Ordenación de Shell

Ordenación de Shell

Ordenación de Shell

La ordenación de Shell pertenece a los métodos de clasificación avanzados, nombrado así en honor del ingeniero y matemático estadounidense Donald Shell que la propuso en 1959.

Este método utiliza una segmentación entre los datos. Funciona comparando elementos que estén distantes; la distancia entre comparaciones decrece conforme el algoritmo se ejecuta hasta la ultima fase, en la cual se comparan los elementos adyacentes, por esta razón se le llama ordenación por disminución de incrementos.

La ordenación de Shell usa una secuencia, h1, h2, . . ., ht, conocida como la secuencia de incrementos. Al principio de todo proceso, se fija una secuencia decreciente de incrementos. Cualquier secuencia funcionará en tanto que empiece con un incremento grande, pero menor al tamaño del arreglo de los datos a ordenar, y que el último valor de dicha secuencia sea 1.

Una elección muy común (pero no tan eficiente) para la secuencia de incrementos es adoptar la secuencia sugerida por Shell: h1 = 1, hn+1 = 3hn+1 .

En la siguiente animación - debido al pequeño tamaño del vector - elegí h1=1, h2=2, h3=3, h4=4, h5=6. Esta es la secuencia de Vaughan Pratt en 1971.

Representación animada de la ordenación de Shell

  1. PROCEDURE tri_Insertion ( Tableau a[1:n],gap,debut)
  2.     POUR i VARIANT DE debut A n AVEC UN PAS gap FAIRE
  3.         INSERER a[i] à sa place dans a[1:i-1];
  4. FIN PROCEDURE;
  5.  
  6. PROCEDURE tri_shell ( Tableau a[1:n])
  7.     POUR gap DANS (6,4,3,2,1) FAIRE
  8.        POUR debut VARIANT DE 0 A gap - 1 FAIRE
  9.           tri_Insertion(Tableau,gap,debut);
  10.        FIN POUR;
  11.     FIN POUR;
  12. FIN PROCEDURE;
  1. let tri_insertion tableau gap debut =
  2.     let i = ref (gap+debut) in
  3.     while (!i < 20) do    
  4.         let en_cours = tableau.(!i) and j = ref (!i - gap) in
  5.             while (!j>=0) && (tableau.(!j)>en_cours) do            
  6.                 tableau.(!j+gap) <-  tableau.(!j);    
  7.                 j := !j - gap;
  8.             done;
  9.             tableau.(!j+gap) <- en_cours;
  10.             i := !i + gap;
  11.     done;;
  12.  
  13. let tri_shell tableau =
  14.     let intervalles = [|6;4;3;2;1|] in
  15.     (* Pour chaque sous-tableau ... *)
  16.     for ngap = 0 to (Array.length intervalles) - 1 do
  17.         let gap = intervalles.(ngap) in
  18.         for debut = 1 to gap do
  19.             (*... on fait un tri par insertion *)
  20.             tri_insertion tableau gap (debut -1);
  21.         done;
  22.     done;
  23. tableau;;
  1. type tab = array[1..20] of integer;
  2. const intervalles : array [1..5] of integer = (6,4,3,2,1);
  3.  
  4. (* Identique à la procedure de tri par insertion classique.
  5. <gap> donne le décalage entre les éléments du sous-tableau
  6. <debut> indique l'index du premier élément du sous-tableau *)
  7. procedure tri_insertion(var tableau : tab; gap : integer; debut : integer) ;
  8.  
  9. var i, j, en_cours : integer;
  10.  
  11. begin
  12.     i := gap + debut;
  13.     while i < 20 do
  14.     begin
  15.         en_cours := tableau[i]; j := i - gap;
  16.         {décalage des éléments du tableau }
  17.         while (j > 0) and (tableau[j] > en_cours) do
  18.         begin
  19.            tableau[j + gap] :=  tableau[j];
  20.            j := j - gap;
  21.         end;
  22.         {on insère l'élément à sa place }
  23.         tableau[j + gap] := en_cours;
  24.         i := i + gap;
  25.     end;
  26. end;
  27.  
  28. procedure tri_shell(var tableau : tab);
  29.  
  30. var i,ngap : integer;
  31.  
  32. begin
  33.     ngap:=1;
  34.     REPEAT
  35.         (* Pour chaque sous-tableau... *)
  36.         for i:=1 to intervalles[ngap] do
  37.         begin
  38.             (*... on fait un tri par insertion *)
  39.             tri_insertion(tableau,intervalles[ngap],i - 1);
  40.         end;
  41.         ngap := ngap + 1;
  42.     UNTIL intervalles[ngap]=1;
  43. end;
  1. def tri_insertion(tableau, gap, debut):
  2.     for i in range(gap + debut,len(tableau),gap):
  3.         en_cours = tableau[i]
  4.         j = i
  5.         #décalage des éléments du tableau }
  6.         while j>0 and tableau[j-gap]>en_cours:
  7.             tableau[j]=tableau[j-gap]
  8.             j = j-gap
  9.         #on insère l'élément à sa place
  10.         tableau[j]=en_cours
  11.  
  12. def tri_shell (tableau):
  13.     for gap in [6,4,3,2,1]:
  14.         # Pour chaque sous-tableau ...
  15.         for debut in range(0,gap):
  16.             #... on fait un tri par insertion
  17.             tri_insertion(tableau,gap,debut)
  1. void tri_insertion(int* t, int gap, int debut)
  2. {
  3.     int j,en_cours;
  4.     for (int i = gap + debut; i < 20; i+=gap) {
  5.         en_cours = t[i];
  6.         for (j = i; j >= gap && t[j - gap] > en_cours; j-=gap) {
  7.             t[j] = t[j - gap];
  8.         }
  9.         t[j] = en_cours;
  10.     }
  11. }
  12.  
  13. void tri_shell(int* t) {
  14.     int intervalles[5]={6,4,3,2,1};
  15.     for (int ngap=0;ngap<5;ngap++) {
  16.         for (int i=0;i<intervalles[ngap];i++)
  17.             tri_insertion(t,intervalles[ngap],i);
  18.     }
  19. }

Les codes présentés ci-dessus ne sont pas les plus orthodoxes... Mais ils conviennent bien pour l'explication de l'algorithme. Vous trouverez des implémentations plus classiques sur rosettacode.org


Use este algoritmo para resolver el pequeño conjunto de la página anterior :



 



La complejidad depende de la secuencia de incrementos. Las siguientes tablas muestran la complejidad en términos de diferentes intervalos. N indica el número de elementos a ordenar , k el número de orden en la secuancia.

Secuencia de espacios (ver Wikipedia)

Shell, 1959

Secuencia Ejemplo Complejidad
$$\left ( \frac{N}{2^{k}} \right )$$1, 3, 6, 12, 25, 50,100 (para N=200) $$\Theta \left ( N^{2} \right )$$

Frank & Lazarus, 1960

Secuencia Ejemplo Complejidad
$$2\left ( \frac{N}{2^{k+1}} \right )+1$$ 1,2,3,4,7,14,26,51,101 (para N=200) $$\Theta \left ( N^{\frac{3}{2}} \right )$$

Hibbard, 1963

Secuencia Ejemplo Complejidad
$$2^{k}-1$$1, 3, 7, 15, 31, 63, 127, 255... (A000225) $$\Theta \left ( N^{\frac{3}{2}} \right )$$

Papernov & Stasevich, 1965

Secuencia Ejemplo Complejidad
$$2^{k}+1$$1, 3, 5, 9, 17, 33, 65, 129, 257... (A083318) $$\Theta \left ( N^{\frac{3}{2}} \right )$$

Pratt (1), 1971

Secuencia Ejemplo Complejidad
Números sucesivos de la forma $$2^{p}3^{q}$$ 1, 2, 3, 4, 6, 8, 9, 12, 16, 18, 24, 27, 32, 36, 48... (A003586) $$\Theta \left ( N\log^{2}N \right )$$

Pratt (2), 1971

Secuencia Ejemplo Complejidad
$$\frac{\left ( 3^{k}-1 \right )}{2}$$, menos que N/3 1, 3, 7, 21, 48, 112, 336, 861, 1968, 4592... (A036569) $$\Theta \left ( N^{\frac{3}{2}} \right )$$

Incerpi & Sedgewick, 1985

Secuencia Ejemplo Complejidad
a(0)=1, then a(s)=a(s-r)*b(r) for r such that C(r, 2) < s ≤ C(r+1, 2), where b() is A0365671, 4, 13, 40, 121, 364, 1093, 3280... (A003462) $$O\left ( N^{1+\sqrt{\frac{8\ln \frac{5}{2}}{\ln N}}} \right )$$

Sedgewick (1), 1986

Secuencia Ejemplo Complejidad
$$4^{k}+3*2^{k-1}+1$$1, 8, 23, 77, 281, 1073, 4193... (A036562) $$O\left ( N^{\frac{4}{3}} \right )$$

Sedgewick (2), 1986

Secuencia Ejemplo Complejidad
$$9\left ( 4^{k-1}-2^{\frac{k}{2}} \right )+1,4^{k+1}-6*2^{\frac{k+1}{2}}+1$$1, 5, 19, 41, 109, 209, 505... (A033622) $$O\left ( N^{\frac{4}{3}} \right )$$

Gonnet & Baeza-Yates, 1991

Secuencia Ejemplo Complejidad
$$h_{k}=\max \left ( \frac{5h_{k-1}}{11}, 1 \right ), h_{0}= N$$1, 2, 4, 9, 19, 41, 91 (pour N=200)

Tokuda, 1992

Secuencia Ejemplo Complejidad
$$\left ( \frac{9^{k}-4^{k}}{5*4^{k-1}} \right )$$1, 4, 9, 20, 46, 103, 233, 525... (A108870)

Ciura, 2001

Secuencia Ejemplo Complejidad
1, 4, 10, 23, 57, 132, 301, 701, 1750 (A102549)

Pigeon (1), 2000

Secuencia Ejemplo Complejidad
1, 2, 19, 103, 311, 691, 1321, 2309, 3671, 5519... (A055875)

Ver Steven Pigeon.

Pigeon(2), 2000

Secuencia Ejemplo Complejidad
$$round\left ( 1+ e^{k-2}\right )$$1, 2, 4, 8, 21, 56, 149, 404, 1098, 2982... (A055876)

Ver Steven Pigeon.


La aplicación Javascript a continuación evalúa el número de intercambios y comparaciones requeridas para el algoritmo. Elija el modo de generación de la secuencia de incrementos, el color de la curva y haga clic en "buscar". Hasta seis curvas se pueden visualizar en el mismo gráfico.

Evaluación de la complejidad de la ordenación de Shell