Shell Sort ordena pequeños subconjuntos con el método de inserción desde un enfoque divide y vencerás.
Recomiendo dominar el método de Ordenación por Inserción.
Análisis
Ordenemos el siguiente grupo de 16 elementos que se muestran a continuación.
Los elementos de cada subconjunto se determinan poniendo un valor de intervalo entre los subíndices de cada grupo.
En este ejemplo utilizaremos un intervalo de 7 elementos.
Nuestro primer subconjunto cuenta con tres elementos (95, 20 y 16) que se ordenan con el método de inserción.
Ahora obtenemos los siguientes tres elementos del segundo subconjunto (25, 54 y 80). Nota que los tres elementos del primer subconjunto ya están ordenados.
El segundo subconjunto esta ordenado por lo que no hay intercambio.
Ahora obtenemos el tercer subconjunto; a partir de el tercer subconjunto todos los subconjuntos tendrán dos elementos.
Nuevamente los elementos del tercer subconjunto se ordenan con el método de inserción. Estas acciones se repiten con todos los subconjuntos y al final el conjunto queda de la siguiente manera:
Ahora vamos a recorrer de nuevo todo el conjunto, pero usaremos un intervalo de 3. Solo habrá tres subconjuntos, el primero con seis valores (16, 60, 68, 83, 63 y 80), el segundo subconjunto tiene los valores () y el tercer subconjunto tiene ().
Al final obtenemos el siguiente conjunto semiordenado.
Finalmente utilizamos un intervalos de 1; en otras palabras, utilizamos el ordenamiento por inserción en todo el conjunto.
Código en C++
void shell(int array[], int size)
{
int i, j, intervalo, temp;
intervalo = size/2;
while (intervalo > 0) {
for (i=intervalo; i < size; i++) {
j = i;
temp = array[i];
while ((j >= intervalo) && (array[j - intervalo] > temp)) {
array[j] = array[j - intervalo];
j = j - intervalo;
}
array[j] = temp;
}
intervalo /= 2;
}
}
Test
#include <iostream>
using namespace std;
void shell(int array[], int size)
{
int i, j, intervalo, temp;
intervalo = size/2;
while (intervalo > 0) {
for (i=intervalo; i < size; i++) {
j = i;
temp = array[i];
while ((j >= intervalo) && (array[j - intervalo] > temp)) {
array[j] = array[j - intervalo];
j = j - intervalo;
}
array[j] = temp;
}
intervalo /= 2;
}
}
int main (int argc, char *argv[])
{
int numeros[] = {95, 25, 83, 97, 71, 18, 68, 20, 54, 40, 60, 27, 63, 96, 16, 80};
/* Imprimimos el arreglo original */
for (int i = 0; i < 16; ++i) {
cout << numeros[i] << " ";
}
cout << endl;
shell(numeros, 16);
/* Imprimimos el arreglo ordenado */
for (int i = 0; i < 16; ++i){
cout << numeros[i] << " ";
}
cout << endl;
}
$ g++ -o ShellSort ShellSort.cpp $ ./ShellSort 95 25 83 97 71 18 68 20 54 40 60 27 63 96 16 80 16 18 20 25 27 40 54 60 63 68 71 80 83 95 96 97