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: h₁ = 1, h_n+1 = 3h_n+1 .

En la siguiente animación - debido al pequeño tamaño del vector - elegí h₁=1, h₂=2, h₃=3, h₄=4, h₅=6. Esta es la secuencia de Vaughan Pratt en 1971.

0 Paso a paso 1 Muy lento 2 Lento3 Velocidad normal4 Rápido 1 Elementos en orden inverso 2 Ordenada elementos 3 Aleatorio 4 Caso peor Ordenar

• Pseudocódigo
• Caml
• Pascal
• Python
• C
• Modelo gráfico
• Diagrama

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 :

Comparaciones :
Movimientos :
 
Mezclar
Resolver

---

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.

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 A036567	1, 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.

1 Caso peor 2 Caso óptimo 3 Caso medio Shell Frank & Lazarus HibbardPapernov & StasevichPratt 1 Pratt 2Incerpi & SedgewickSedgewick 1Sedgewick 2Gonnet & Baeza-YatesTokudaCiura Pigeon 1Pigeon 2No (ordenamiento por inserción) Albaricoque Trigo CaféDrilEscarlataFresa WistariaHeliotropoAñil Buscar Borrar

---