Shellsort

Swapping pares de elementos en sucesivos pasos de Shellsort con huecos 5, 3, 1

Shellsort, también conocido como Shell sort o método de Shell, es una clasificación de comparación in situ. Puede verse como una generalización de la clasificación por intercambio (clasificación de burbuja) o la clasificación por inserción (clasificación de inserción). El método comienza clasificando pares de elementos separados entre sí, y luego reduce progresivamente la brecha entre los elementos que se compararán. Al comenzar con elementos muy separados, puede mover algunos elementos fuera de lugar a su posición más rápido que un simple intercambio de vecinos más cercano. Donald Shell publicó la primera versión de este tipo en 1959. El tiempo de ejecución de Shellsort depende en gran medida de la secuencia de intervalos que utiliza. Para muchas variantes prácticas, determinar su complejidad temporal sigue siendo un problema abierto.

Descripción

Shellsort es una optimización de la ordenación por inserción que permite el intercambio de elementos que están muy separados. La idea es organizar la lista de elementos de modo que, comenzando en cualquier lugar, tomando cada hésimo elemento produzca una lista ordenada. Se dice que una lista de este tipo está ordenada por h. También se puede considerar como h listas intercaladas, cada una ordenada individualmente. Comenzar con valores grandes de h permite que los elementos se desplacen largas distancias en la lista original, lo que reduce grandes cantidades de desorden rápidamente y deja menos trabajo para los pasos de clasificación de h más pequeños.. Si la lista se ordena k para algún número entero más pequeño k, entonces la lista permanece ordenada por h. Siguiendo esta idea de una secuencia decreciente de valores h que terminan en 1, se garantiza que se dejará una lista ordenada al final.

En términos simples, esto significa que si tenemos una matriz de 1024 números, nuestro primer espacio (h) podría ser 512. Luego revisamos la lista comparando cada elemento en la primera mitad con el elemento en la segunda mitad. Nuestro segundo espacio (k) es 256, que divide la matriz en cuatro secciones (comenzando en 0,256,512,768), y nos aseguramos de que los primeros elementos de cada sección estén ordenados entre sí, luego el segundo elemento en cada sección, y así sucesivamente. En la práctica, la secuencia de intervalos podría ser cualquier cosa, pero el último intervalo siempre es 1 para finalizar la ordenación (finalizando efectivamente con una ordenación por inserción normal).

A continuación se muestra un ejemplo de ejecución de Shellsort con espacios 5, 3 y 1.

La primera pasada, clasificación por 5, realiza la clasificación por inserción en cinco subarreglos separados (a₁, a₆, a₁₁), (a₂, a ₇, a₁₂), (a₃, a ₈), (a₄, a₉), ( a₅, a₁₀). Por ejemplo, cambia el subarreglo (a₁, a₆, a ₁₁) de (62, 17, 25) a (17, 25, 62). El siguiente paso, clasificación por 3, realiza la clasificación por inserción en los tres subarreglos (a₁, a₄, a₇, a₁₀), (a₂, a₅, a₈, a₁₁), (a₃, a₆, a₉, a₁₂). El último paso, clasificación 1, es una clasificación de inserción ordinaria de la matriz completa (a₁,..., a ₁₂).

Como ilustra el ejemplo, los subarreglos en los que opera Shellsort son inicialmente cortos; luego son más largos pero casi ordenados. En ambos casos, la ordenación por inserción funciona de manera eficiente.

Shellsort no es estable: puede cambiar el orden relativo de los elementos con valores iguales. Es un algoritmo de clasificación adaptativo en el sentido de que se ejecuta más rápido cuando la entrada se clasifica parcialmente.

Pseudocódigo

Usando la secuencia de intervalos de Marcin Ciura, con una ordenación por inserción interna.

# Ordenar un array a[0...n-1].deficiencias = [701, 301, 132, 57, 23, 10, 4, 1] / Ciura secuencia de brecha# Empieza con la brecha más grande y trabaja hasta una brecha de 1# similar to insertion kind but instead of 1, gap is being used in each stepen adelante ()brecha dentro deficiencias){} # Haga un tipo de inserción en gapped para cada elemento en las lagunas # Cada bucle deja un [0.gap-1] en orden accionado para ()i = brecha; i . n; i += 1) {} # Guardar a[i] en tiempo y hacer un agujero en la posición i tempestad = a[i] # desplazar elementos surtidos antes hasta que se encuentre la ubicación correcta para a[i] para ()j = i; ()j >= brecha) " ()a[j - brecha] ■ tempestad); j -= brecha) {} a[j] = a[j - brecha] } # put temp (el original a[i]) en su ubicación correcta a[j] = tempestad }}

Secuencias de intervalos

La cuestión de decidir qué secuencia de intervalos usar es difícil. Cada secuencia de huecos que contiene 1 produce una ordenación correcta (ya que esto hace que el paso final sea una ordenación por inserción ordinaria); sin embargo, las propiedades de las versiones de Shellsort así obtenidas pueden ser muy diferentes. Muy pocos espacios ralentizan los pases y demasiados espacios producen una sobrecarga.

La siguiente tabla compara la mayoría de las secuencias de brechas propuestas publicadas hasta el momento. Algunos de ellos tienen elementos decrecientes que dependen del tamaño de la matriz ordenada (N). Otras son secuencias infinitas crecientes, cuyos elementos menores que N deben usarse en orden inverso.

OEIS	General term (k ≥ 1)	Concrete gaps	Worst-case time complexity	Author and year of publication
	⌊ N 2 k ⌋ {displaystyle leftlfloor {frac {N}{2^{k}}}rightrfloor }	⌊ N 2 ⌋ , ⌊ N 4 ⌋ , … , 1 {displaystyle leftlfloor {frac {N}{2}}rightrfloorleftlfloor {frac {N}{4}}rightrfloorldots1}	Θ ( N 2 ) {displaystyle Theta left(N^{2}right)} [e.g. when N = 2p]	Shell, 1959
	2 ⌊ N 2 k + 1 ⌋ + 1 {displaystyle 2leftlfloor {frac {N}{2^{k+1}}}rightrfloor +1}	2 ⌊ N 4 ⌋ + 1 , … , 3 , 1 {displaystyle 2leftlfloor {frac {N}{4}}rightrfloor +1,ldots3,1}	Θ ( N 3 2 ) {displaystyle Theta left(N^{frac {3}{2}}right)}	Frank & Lazarus, 1960
A000225	2 k − 1 {displaystyle 2^{k}-1}	1 , 3 , 7 , 15 , 31 , 63 , … {displaystyle 1,3,7,15,31,63,ldots }	Θ ( N 3 2 ) {displaystyle Theta left(N^{frac {3}{2}}right)}	Hibbard, 1963
A083318	2 k + 1 {displaystyle 2^{k}+1} , prefixed with 1	1 , 3 , 5 , 9 , 17 , 33 , 65 , … {displaystyle 1,3,5,9,17,33,65,ldots }	Θ ( N 3 2 ) {displaystyle Theta left(N^{frac {3}{2}}right)}	Papernov & Stasevich, 1965
A003586	Successive numbers of the form 2 p 3 q {displaystyle 2^{p}3^{q}} (3-smooth numbers)	1 , 2 , 3 , 4 , 6 , 8 , 9 , 12 , … {displaystyle 1,2,3,4,6,8,9,12,ldots }	Θ ( N log 2 ⁡ N ) {displaystyle Theta left(Nlog ^{2}Nright)}	Pratt, 1971
A003462	3 k − 1 2 {displaystyle {frac {3^{k}-1}{2}}} , not greater than ⌈ N 3 ⌉ {displaystyle leftlceil {frac {N}{3}}rightrceil }	1 , 4 , 13 , 40 , 121 , … {displaystyle 1,4,13,40,121,ldots }	Θ ( N 3 2 ) {displaystyle Theta left(N^{frac {3}{2}}right)}	Knuth, 1973, based on Pratt, 1971
A036569	∏ I a q , where a 0 = 3 a q = min { n ∈ N : n ≥ ( 5 2 ) q + 1 , ∀ p : 0 ≤ p < q ⇒ gcd ( a p , n ) = 1 } I = { 0 ≤ q < r ∣ q ≠ 1 2 ( r 2 + r ) − k } r = ⌊ 2 k + 2 k ⌋ {displaystyle {begin{aligned}&prod limits _{I}a_{q},{hbox{where}}\a_{0}={}&3\a_{q}={}&min left{nin mathbb {N} colon ngeq left({frac {5}{2}}right)^{q+1},forall pcolon 0leq p<qRightarrow gcd(a_{p},n)=1right}\I={}&left{0leq q<rmid qneq {frac {1}{2}}left(r^{2}+rright)-kright}\r={}&leftlfloor {sqrt {2k+{sqrt {2k}}}}rightrfloor end{aligned}}}	1 , 3 , 7 , 21 , 48 , 112 , … {displaystyle 1,3,7,21,48,112,ldots }	O ( N 1 + 8 ln ⁡ ( 5 / 2 ) ln ⁡ ( N ) ) {displaystyle Oleft(N^{1+{sqrt {frac {8ln left(5/2right)}{ln(N)}}}}right)}	Incerpi & Sedgewick, 1985, Knuth
A036562	4 k + 3 ⋅ 2 k − 1 + 1 {displaystyle 4^{k}+3cdot 2^{k-1}+1} , prefixed with 1	1 , 8 , 23 , 77 , 281 , … {displaystyle 1,8,23,77,281,ldots }	O ( N 4 3 ) {displaystyle Oleft(N^{frac {4}{3}}right)}	Sedgewick, 1982
A033622	{ 9 ( 2 k − 2 k 2 ) + 1 k even , 8 ⋅ 2 k − 6 ⋅ 2 ( k + 1 ) / 2 + 1 k odd {displaystyle {begin{cases}9left(2^{k}-2^{frac {k}{2}}right)+1&k{text{ even}},\8cdot 2^{k}-6cdot 2^{(k+1)/2}+1&k{text{ odd}}end{cases}}}	1 , 5 , 19 , 41 , 109 , … {displaystyle 1,5,19,41,109,ldots }	O ( N 4 3 ) {displaystyle Oleft(N^{frac {4}{3}}right)}	Sedgewick, 1986
	h k = max { ⌊ 5 h k − 1 − 1 11 ⌋ , 1 } , h 0 = N {displaystyle h_{k}=max left{leftlfloor {frac {5h_{k-1}-1}{11}}rightrfloor1right},h_{0}=N}	⌊ 5 N − 1 11 ⌋ , ⌊ 5 11 ⌊ 5 N − 1 11 ⌋ − 1 ⌋ , … , 1 {displaystyle leftlfloor {frac {5N-1}{11}}rightrfloorleftlfloor {frac {5}{11}}leftlfloor {frac {5N-1}{11}}rightrfloor -1rightrfloorldots1}	Un­known	Gonnet & Baeza-Yates, 1991
A108870	⌈ 1 5 ( 9 ⋅ ( 9 4 ) k − 1 − 4 ) ⌉ {displaystyle leftlceil {frac {1}{5}}left(9cdot left({frac {9}{4}}right)^{k-1}-4right)rightrceil }	1 , 4 , 9 , 20 , 46 , 103 , … {displaystyle 1,4,9,20,46,103,ldots }	Un­known	Tokuda, 1992
A102549	Unknown (experimentally derived)	1 , 4 , 10 , 23 , 57 , 132 , 301 , 701 {displaystyle 1,4,10,23,57,132,301,701}	Un­known	Ciura, 2001

Cuando la representación binaria de N contiene muchos ceros consecutivos, Shellsort usando la secuencia de intervalos original de Shell genera Θ(N²) comparaciones en el peor de los casos. Por ejemplo, este caso ocurre para N igual a una potencia de dos cuando los elementos mayores y menores que la mediana ocupan posiciones pares e impares respectivamente, ya que se comparan solo en el último paso.

Aunque tiene mayor complejidad que el O(N log N) que es óptimo para ordenar comparaciones, la versión de Pratt se presta para clasificar redes y tiene la misma complejidad de puerta asintótica que el clasificador bitónico de Batcher.

Gonnet y Baeza-Yates observaron que Shellsort hace la menor cantidad de comparaciones en promedio cuando las proporciones de brechas sucesivas son aproximadamente iguales a 2,2. Esta es la razón por la que su secuencia con una proporción de 2,2 y la secuencia de Tokuda con una proporción de 2,25 resultan eficientes. Sin embargo, no se sabe por qué esto es así. Sedgewick recomienda usar espacios que tengan un máximo común divisor bajo o que sean coprimos por pares.

Con respecto al número promedio de comparaciones, la secuencia de Ciura tiene el rendimiento más conocido; las brechas de 701 no se determinaron, pero la secuencia se puede ampliar más de acuerdo con la fórmula recursiva hk=⌊ ⌊ 2.25hk− − 1⌋ ⌋ {displaystyle ¿Qué? 2.25h_{k-1}rfloor }.

La secuencia de Tokuda, definida por la simple fórmula hk=⌈ ⌈ hk.⌉ ⌉ {displaystyle H_{k}=lceil ¿Qué?, donde hk.=2.25hk− − 1.+1{displaystyle ¿Qué?, h1.=1{displaystyle h'_{1}=1}, se puede recomendar para aplicaciones prácticas.

Si el tamaño de entrada máximo es pequeño, como puede ocurrir si se utiliza Shellsort en subarreglos pequeños por otro algoritmo de clasificación recursivo, como clasificación rápida o clasificación combinada, entonces es posible tabular una secuencia óptima para cada tamaño de entrada.

Complejidad computacional

La siguiente propiedad se cumple: después de la clasificación h₂ de cualquier matriz clasificada h₁, el la matriz permanece ordenada h₁. Cada matriz ordenada h₁ y h₂ también es (a ₁h₁+a₂h₂), para cualquier número entero no negativo a₁ y a₂. Por lo tanto, la complejidad del caso peor de Shellsort está relacionada con el problema de Frobenius: para números enteros h₁,..., h_n con mcd = 1, el número de Frobenius g(h₁,..., h _n) es el entero mayor que no se puede representar como a₁h₁+... +a_nh_n con entero no negativo a₁,..., un_n. Utilizando fórmulas conocidas para los números de Frobenius, podemos determinar la complejidad de Shellsort en el peor de los casos para varias clases de secuencias de intervalos. Los resultados probados se muestran en la tabla anterior.

Mark Allen Weiss demostró que Shellsort se ejecuta en tiempo O(N log N) cuando la matriz de entrada está en orden inverso.

Con respecto al número medio de operaciones, ninguno de los resultados comprobados se refiere a una secuencia práctica de brechas. Para brechas que son poderes de dos, Espelid computó este promedio como 0,5349NN− − 0.4387N− − 0,097N+O()1){displaystyle 0.5349N{sqrt {N}-0.4387N-0.097{sqrt {N}+O(1)}. Knuth determinó la complejidad promedio de ordenar un N-element array with two gaps (h, 1) ser 2N2h+π π N3h{displaystyle {frac {2N^{2}{h}+{sqrt {pi N^{3}h}}. Sigue que un Shellsort de dos pasos con h =N^1/3) hace en promedio O()N^5/3) comparaciones/inversiones/tiempo de funcionamiento. Yao encontró la complejidad promedio de un Shellsort de tres pasos. Su resultado fue refinado por Janson y Knuth: el número promedio de comparaciones/inversiones/tiempo de funcionamiento realizado durante un Shellsort con tres brechas (ch, cg, 1), donde h y g son coprime, es N24ch+O()N){displaystyle {frac {fnK}{4ch}+O(N)} en el primer paso, 18gπ π ch()h− − 1)N3/2+O()hN){fnMicroc {fnK} {fnMicroc} {fnMicroc} {fn} {fn} {fnMicroc}} {fn}}} {fnMicroc} {fnMicroc} ♪ ¿Qué? en el segundo paso y ↑ ↑ ()h,g)N+18π π c()c− − 1)N3/2+O()()c− − 1)gh1/2N)+O()c2g3h2){displaystyle psi (h,g)N+{frac {1}{8}{sqrt {frac] # ¿Qué? en el tercer paso. ↑()h, g) en la última fórmula es una función complicada asintoticamente igual a π π h128g+O()g− − 1/2h1/2)+O()gh− − 1/2){displaystyle {sqrt {frac {pih}}g+Oleft(g^{-1/2}h^{1/2}right)+Oleft(gh^{-1/2}right)}. En particular, cuando h =N^7/15) y g =N^1/5), el tiempo promedio de clasificación es O()N^23/15).

Según los experimentos, se conjetura que Shellsort con la secuencia de intervalos de Hibbard se ejecuta en O(N^5/4) tiempo promedio, y que la secuencia de Gonnet y Baeza-Yates requiere en promedio 0.41N ln N (ln ln N + 1/ 6) movimiento de elementos. Las aproximaciones del número promedio de operaciones presentadas anteriormente para otras secuencias fallan cuando las matrices ordenadas contienen millones de elementos.

El gráfico siguiente muestra el número promedio de comparaciones de elementos en varias variantes de Shellsort, divididas por el límite inferior teórico, es decir, log₂N!, donde la secuencia 1, 4, 10, 23, 57, 132, 301, 701 se ha extendido de acuerdo a la fórmula hk=⌊ ⌊ 2.25hk− − 1⌋ ⌋ {displaystyle ¿Qué? 2.25h_{k-1}rfloor }.

Aplicando la teoría de la complejidad de Kolmogorov, Jiang, Li y Vitányi comprobó el siguiente límite inferior para el orden del número medio de operaciones/tiempo de funcionamiento en un p-pass Shellsort: Ω(pN^1+1/pCuando p≤ log₂N y Ω(pNCuando p log log₂N. Por lo tanto, Shellsort tiene perspectivas de correr en un tiempo promedio que crece asintomáticamente como N logN sólo cuando se utilizan secuencias de brechas cuyo número de brechas crece en proporción al logaritmo del tamaño de la matriz. Sin embargo, se desconoce si Shellsort puede llegar a este orden asintotico de complejidad promedio, lo que es óptimo para los tipos de comparación. El límite inferior fue mejorado por Vitányi para cada número de pases p{displaystyle p} a Ω Ω ()N.. k=1phk− − 1/hk){displaystyle Omega (Nsum _{k=1} {p}h_{k-1}/h_{k}}Donde h0=N{displaystyle H_{0}=N}. This result implies for example the Jiang-Li-Vitányi lower bound for all p{displaystyle p}-pasa aumento de secuencias y mejora que menor límite para determinadas secuencias de aumento. De hecho, todos los límites (más bajos y superiores) conocidos actualmente por el caso promedio son exactamente igualados por este límite inferior. Por ejemplo, esto da el nuevo resultado de que el límite superior Janson-Knuth es igualado por el límite inferior resultante para la secuencia de aumento usado, mostrando que tres pase Shellsort para esta secuencia de aumento utiliza .. ()N23/15){displaystyle Theta (N^{23/15})} comparaciones/inversiones/tiempo de funcionamiento. La fórmula nos permite buscar secuencias de aumento que rindan límites inferiores que son desconocidos; por ejemplo, una secuencia de aumento para cuatro pases que tiene un límite inferior superior a Ω Ω ()pn1+1/p)=Ω Ω ()n5/4){displaystyle Omega (pn^{1+1/p})=Omega (n^{5/4})} para la secuencia de aumento h1=n11/16,{displaystyle h_{1}=n^{11/16},} h2=n7/16,{displaystyle h_{2}=n^{7/16},} h3=n3/16,{displaystyle h_{3}=n^{3/16},} h4=1{displaystyle h_{4}=1}. El límite inferior se convierte T=Ω Ω ()n⋅ ⋅ ()n1− − 11/16+n11/16− − 7/16+n7/16− − 3/16+n3/16)=Ω Ω ()n1+5/16)=Ω Ω ()n21/16).{displaystyle T=Omega (ncdot (n^{1-11/16}+n^{11/16-7/16}+n^{7/16-3/16}+n^{3/16})=Omega (n^{1+5/16})=Omega (n^{21/16}). }

La peor complejidad de cualquier versión de Shellsort es de orden superior: Plaxton, Poonen y Suel mostraron que crece al menos tan rápido como Ω Ω ()N()log⁡ ⁡ Nlog⁡ ⁡ log⁡ ⁡ N)2){displaystyle Omega left(Nleft({log N over log N}right)^{2}right)}. Robert Cypher demostró un límite más bajo: Ω Ω ()N()log⁡ ⁡ N)2log⁡ ⁡ log⁡ ⁡ N){displaystyle Omega left (N{(log N)^{2} over {log log N}right)} cuando h_{s}}" xmlns="http://www.w3.org/1998/Math/MathML">hs+1■hs{displaystyle ¿Qué?h_{s}}" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/45d4172549854db33baa4bb93c3229148694635c" style="vertical-align: -0.671ex; width:9.884ex; height:2.509ex;"/> para todos s{displaystyle s}.

Aplicaciones

Shellsort realiza más operaciones y tiene una proporción de errores de caché más alta que Quicksort. Sin embargo, dado que se puede implementar usando poco código y no usa la pila de llamadas, algunas implementaciones de la función qsort en la biblioteca estándar de C destinadas a sistemas integrados la usan en lugar de la ordenación rápida. Shellsort se usa, por ejemplo, en la biblioteca uClibc. Por razones similares, en el pasado, Shellsort se usaba en el kernel de Linux.

Shellsort también puede servir como subalgoritmo de ordenación introspectiva, para ordenar subarreglos cortos y evitar una ralentización cuando la profundidad de recursión supera un límite determinado. Este principio se emplea, por ejemplo, en el compresor bzip2.