Método Shell
Existen varias formas de calcular el intervalo, lo cual puede
mejorar la efectividad del algoritmo. A continuación, explicaremos
la secuencia original propuesta por Shell: n/2, n/4…, n/n, es decir,
uno (dividir entre dos, hasta que el último intervalo sea uno),
donde n es el tamaño del arreglo.
Observa el siguiente ejemplo, donde se aclara a detalle lo
planteado anteriormente; en él podrás observar los pasos para
llevar a cabo este tipo de ordenamiento sobre el arreglo
desordenado:
Haz clic en cada número o en las flechas para desplegar el
contenido.
1
Se realiza la ordenación, primero tomando como valor inicial de intervalo 4;
es decir, como el número de elementos n es 8, tenemos que n/2 = 4.
Podemos decir también que en esta primera interacción dividimos el
arreglo en cuatro subarreglos: {15,35}, {33,19}, {27,42} y {10,44}.
5.10. El ordenamiento de Shell
El ordenamiento de Shell, a veces llamado “ordenamiento de incremento decreciente”,
mejora el ordenamiento por inserción al romper la lista original en varias sublistas más
pequeñas, cada una de las cuales se ordena mediante un ordenamiento por inserción. La
manera única en que se eligen estas sublistas es la clave del ordenamiento de Shell. En
lugar de dividir la lista en sublistas de ítems contiguos, el ordenamiento de Shell usa un
incremento i, a veces denominado brecha, para crear una sublista eligiendo todos los
ítems que están separados por i ítems.
Este proceso se puede ver en la Figura 6. La lista tiene nueve ítems. Si usamos un
incremento de tres, hay tres sublistas, cada una de las cuales puede ordenarse mediante
un ordenamiento por inserción. Después de completar estos ordenamientos, obtenemos
la lista que se muestra en la Figura 7. Aunque esta lista no está completamente
ordenada, ha ocurrido algo muy interesante. Al ordenar las sublistas, hemos acercado
los ítems a donde realmente pertenecen.
Figura 6: Un ordenamiento de Shell con incrementos de tres
Figura 6: Un ordenamiento de Shell con incrementos de tres
Figura 7: Un ordenamiento de Shell después de ordenar cada sublista
Figura 7: Un ordenamiento de Shell después de ordenar cada sublista
La Figura 8 muestra un ordenamiento por inserción final que usa un incremento de uno;
en otras palabras, un ordenamiento por inserción estándar. Note que mediante la
realización anticipada de los ordenamientos de las sublistas, hemos reducido el número
total de operaciones de desplazamiento necesarias para poner la lista en su orden
definitivo. Para este caso, sólo necesitamos cuatro desplazamientos más para completar
el proceso.
Figura 8: Ordenamiento de Shell: Un ordenamiento por inserción final con incremento
de 1
Figura 8: Ordenamiento de Shell: Un ordenamiento por inserción final con incremento
de 1
Figura 9: Sublistas iniciales para el ordenamiento de Shell
Figura 9: Sublistas iniciales para el ordenamiento de Shell
Dijimos antes que la forma en que se eligen los incrementos es la característica única
del ordenamiento de Shell. La función mostrada en el ActiveCode 1 utiliza un conjunto
diferente de incrementos. En este caso, comenzamos con n2𝑛2 sublistas. En la siguiente
pasada, se ordenan n4𝑛4 sublistas. Eventualmente, se ordena una sola lista con el
ordenamiento por inserción básico. La Figura 9 muestra las primeras sublistas para
nuestro ejemplo usando este incremento.
La siguiente invocación a la función ordenamientoDeShell muestra las listas
parcialmente ordenadas después de cada incremento, siendo el ordenamiento final un
ordenamiento por inserción con un incremento de uno.
Save & RunLoad HistoryShow CodeLens
Método Shell
El ordenamiento Shell (Shell sort en inglés) es
un algoritmo de ordenamiento. El método se
denomina Shell en honor de su inventor Donald
Shell. Su implementación original,
requiere comparaciones e intercambios en el peor
caso. Un cambio menor presentado en el libro de V.
Pratt produce una implementación con un
rendimiento de O en el peor caso. Esto es mejor que
las comparaciones requeridas por algoritmos
simples pero peor que el óptimo. Aunque es fácil
desarrollar un sentido intuitivo de cómo funciona
este algoritmo, es muy difícil analizar su tiempo de
ejecución.
El Shell sort es una generalización del ordenamiento
por insercion:
1. El ordenamiento por inserción es
eficiente si la entrada está "casi
ordenada".
2. El ordenamiento por inserción es
ineficiente, en general, porque mueve
los valores sólo una posición cada vez.
El algoritmo Shell sort mejora el ordenamiento por
inserción comparando elementos separados por un
espacio de varias posiciones. Esto permite que un
elemento haga "pasos más grandes" hacia su
posición esperada. Los pasos múltiples sobre los
datos se hacen con tamaños de espacio cada vez
más pequeños. El último paso del Shell sort es un
simple ordenamiento por inserción, pero para
entonces, ya está garantizado que los datos del
vector están casi ordenados.
Ejemplo:
Considere un valor pequeño que está inicialmente
almacenado en el final del vector. Usando un
ordenamiento O(n2) como el ordenamiento de
burbuja o el ordenamiento por insercion, tomará
aproximadamente n comparaciones e intercambios
para mover este valor hacia el otro extremo del
vector. El Shell sort primero mueve los valores
usando tamaños de espacio gigantes, de manera
que un valor pequeño se moverá bastantes
posiciones hacia su posición final, con sólo unas
pocas comparaciones e intercambios.
Uno puede visualizar el algoritmo Shell sort de la
siguiente manera: coloque la lista en una tabla y
ordene las columnas (usando un ordenamiento por
insercion). Repita este proceso, cada vez con un
número menor de columnas más largas. Al final, la
tabla tiene sólo una columna. Mientras que
transformar la lista en una tabla hace más fácil
visualizarlo, el algoritmo propiamente hace su
ordenamiento en contexto (incrementando el índice
por el tamaño de paso, esto es usando i +=
tamaño_de_paso en vez dei++).
Por ejemplo, considere una lista de números como [
13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10 ]. Si
comenzamos con un tamaño de paso de 5,
podríamos visualizar esto dividiendo la lista de
números en una tabla con 5 columnas. Esto
quedaría así:
25 59 94 65 23
45 27 73 25 39
10
Entonces ordenamos cada columna, lo que nos da
10 14 73 25 23
13 27 94 33 39
25 59 94 65 82
45
Cuando lo leemos de nuevo como una única lista de
números, obtenemos[10 14 73 25 23 13 27 94 33 39
25 59 94 65 82 45]. Aquí, el 10 que estaba en el
extremo final, se ha movido hasta el estremo inicial.
Esta lista es entonces de nuevo ordenada usando
un ordenamiento con un espacio de 3 posiciones, y
después un ordenamiento con un espacio de 1
posición (ordenamiento por inserción simple).
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 = 1, hn+1 = 3hn+1 .
En la siguiente animación - debido al pequeño tamaño del vector - elegí h 1=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
0 Paso a paso 3 Velocidad normal 3 Aleatorio 4 Caso
peor
Algoritmo de clasificación de shell
Los pasos o procedimiento para el algoritmo de clasificación de
shell son los siguientes:
Paso 1) Inicialice el valor del intervalo, h = n/2. (En este ejemplo, n
es el tamaño de la matriz)
Paso 2) Coloque todos los elementos dentro de una distancia del
intervalo h en una sublista.
Paso 3) Ordene esas sublistas mediante ordenación por inserción.
Paso 4) Establezca un nuevo intervalo, h=h/2.
Paso 5) Si h>0, vaya al paso 2. En caso contrario, vaya al paso 6.
Paso 6) La salida resultante será la matriz ordenada.
Cómo funciona la clasificación de shell
En la ordenación por inserción, los elementos se mueven solo una
posición a la vez. Por el contrario, la ordenación de shell divide la
matriz en partes más pequeñas según el valor del intervalo y
ejecuta la ordenación por inserción en esas partes.
Gradualmente, el valor del intervalo disminuye y el tamaño de las
piezas divididas aumenta. Como las piezas se clasifican
individualmente de antemano, fusionarlas requiere menos pasos
que el proceso. tipo de inserción.
El following GIF muestra una demostración de la clasificación de
conchas. En esta demostración, el valor indicado en rojo y azul se
compara e intercambia según el orden de inserción. Luego, el
intervalo disminuye y la ordenación de shell inicia la ordenación
por inserción en esos datos casi ordenados.
Funcionamiento del algoritmo de
clasificación de Shell
Veamos un [Link] ejemplo de un algoritmo de
clasificación de shell. En este ejemplo, ordenaremos lo
siguientewing matriz usando ordenación de shell:
Paso 1) Aquí, el tamaño de la matriz es 8. Por lo tanto, el valor del
intervalo será h = 8/2 o 4.
Paso 2) Ahora, almacenaremos todos los elementos a una distancia
de 4. Para nuestro caso, las sublistas son: {8, 1}, {6, 4}, {7, 5}, {2, 3}.
Paso 3) Ahora, esas sublistas se ordenarán mediante ordenación
por inserción, donde se usa una variable temporal para comparar
ambas. numbers y ordenar en consecuencia.
La matriz sería como la [Link] después del intercambio
operaciones-
Paso 4) Ahora, disminuiremos el valor inicial del intervalo. El nuevo
intervalo será h=h/2 o 4/2 o 2.
Paso 5) Como 2>0, iremos al paso 2 para almacenar todos los
elementos a una distancia de 2. Para este momento, las sublistas
son:
{1, 5, 8, 7}, {4, 2, 6, 3}
Luego, estas sublistas se ordenarán mediante ordenación por
inserción. Después de comparar e intercambiar la primera sublista,
la matriz sería la siguientewing.
Después de ordenar la segunda sublista, la matriz original será:
Por otra parte, el intervalo se reducirá. Ahora el intervalo será h=h/2
o 2/1 o 1. Por lo tanto, usaremos el algoritmo de ordenación por
inserción para ordenar la matriz modificada.
Following es la descripción del procedimiento paso a paso del tipo
de inserción.
El intervalo se divide nuevamente por 2. En ese momento, el
intervalo se vuelve 0. Entonces vamos al paso 6.
Paso 6) Como el intervalo es 0, la matriz se ordena por este tiempo.
La matriz ordenada es-
Pseudocódigo
Start
Input array an of size n
for (interval = n / 2; interval & gt; 0; interval /= 2)
for (i = interval; i & lt; n; i += 1)
temp = a[i];
for (j = i; j & gt; = interval & amp; & amp; a[j - interval] & gt; temp; j -= interval)
a[j] = a[j - interval];
a[j] = temp;
End
Programa de clasificación de Shell en C/C++
Entrada:
//Shell Sort Program in C/C++
#include <bits/stdc++.h>
using namespace std;
void ShellSort(int data[], int size) {
for (int interval = size / 2; interval > 0; interval /= 2) {
for (int i = interval; i < size; i += 1) {
int temp = data[i];
int j;
for (j = i; j >= interval && data[j - interval] > temp; j -= interval) {
data[j] = data[j - interval];
}
data[j] = temp;
}
}
}
int main() {
int data[] = {8, 6, 7, 2, 1, 4, 5, 3};
int size = sizeof(data) / sizeof(data[0]);
ShellSort(data, size);
cout << "Sorted Output: \n";
for (int i = 0; i < size; i++)
cout << data[i] << " ";
cout << "\n";
}
Salida:
Sorted Output:
12345678
