El Shell sort es una generalización del ordenamiento por inserción, teniendo en
cuenta dos observaciones:
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.
La ordenación por inserción no funciona bien cuando los elementos cercanos
están muy separados. Shell sort ayuda a reducir la distancia entre los elementos
cercanos. Por lo tanto, habrá menos intercambios a realizar.
La lógica de ordenación de shell es ordenar primero las entradas que están más
alejadas. Dada una lista parcialmente ordenada, en teoría puede ordenar mucho
más rápido que O (n ^ 2). También dada una gran matriz sin ordenar, la
probabilidad de que su posición ordenada final esté lejos de su posición actual es
alta. Entonces, lógicamente, tiene sentido usar una brecha más grande.
Pero el punto principal de los tipos de shell no es realmente su rendimiento, sino la
simplicidad del algoritmo y el bajo uso de la memoria de pila.
Dado que, en promedio, funciona mejor que O(n^2) (depende de la secuencia de
intervalos), tamaños de código pequeños y usos de pila, es muy popular en
aplicaciones integradas donde las limitaciones de memoria son un factor
En pocas palabras, Shell sort se encarga de reducir el intervalo de dos
valores muy lejanos dentro de un arreglo en cada comparación.
Considere un valor pequeño que está inicialmente almacenado en el final del vector que se quiere
ordenar de forma ascendente. Usando un ordenamiento O(n2) como el ordenamiento de burbuja
o el ordenamiento por inserción, 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 solo 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 inserción). Repita este proceso, cada vez con
un número menor de columnas más largas. Al final, la tabla tiene solo 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 de i++).
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í:
13 14 94 33 82
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
extremo 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).
El Shell sort lleva este nombre en honor a su inventor, Donald Shell, que lo publicó en 1959.
Algunos libros de texto y referencias antiguas le llaman ordenación "Shell-Metzner" por Marlene
Metzner Norton, pero según Metzner, "No tengo nada que ver con el algoritmo de ordenamiento,
y mi nombre nunca debe adjuntarse a éste." [
Objetivo:
Ordenar un número finito de elementos en un tiempo razonable.
Características:
Es un algoritmo de ordenación interna, esto quiere decir que los datos son alojados en memoria
principal.
Se basa en comparaciones e Iteraciones.
Requiere que el tiempo de acceso a cualquier dato sea constante (ideado para trabajar con arrays,
arrays de punteros, etc.). En estructuras y listas enlazadas el tiempo de acceso no es constante.
No necesita espacio adicional para realizar el ordenamiento del arreglo.
Eficaz cuando se implementa en arrays no muy grandes.
Sirve también para ordenar otro tipo de datos aparte de enteros, pero hay que tener en claro el
concepto de la ordenación para implementar correctamente.
