Algoritmo Shell Short

El ordenamiento Shell Short fue publicado en la revista Communications of the ACM en el año 1959, y se llamo así por el Ingeniero matemático Donald Shell.

¿Como se define el algoritmo?Es un algoritmo de ordenación interna sencillo pero ingenioso, basado en comparaciones e intercambios. 

- Sus resultados son radicalmente mejores que los que se pueden obtener con el método.

- žEs un algoritmo que casi no se usa por las siguientes causas:

-žPara su comprensión requiere un cierto esfuerzo y algo de tiempo, y se suele centrar la atención en los tres algoritmos más básicos (burbuja, selección e inserción)

-l al-El algoritmo QuickSort (desarrollado por Hoare en 1962) puede dar mejores resultados pero puede “perjudicar” un poco en la programación básica. 

ž- žShellSort, es el mejor algoritmo de ordenación, en los que la cantidad de memoria adicional que necesita (aparte de los propios datos a ordenar) es constante, sea cual sea la cantidad de datos a ordenar.

-žEl algoritmo de la burbuja, el de selección directa, el de inserción directa y el de Shell son todos in-situ.

-žOtros métodos de ordenación, como QuickSort, BinSort, HeapSort o RadixSort pueden pueden superar a ShellSort en cuanto al tiempo de ejecución, pero ninguno es algoritmo in-situ. 

- žEs necesario gestionar una cantidad adicional de memoria proporcional al tamaño de los datos a ordenar.

  

Características:  

ž-Se trata de un algoritmo de ordenación interna. Al igual que cualquier otro de ordenación interna (los datos están en memoria principal) 

ž-Se basa en comparaciones e intercambios. 

-žNecesita que el tiempo de acceso a cualquier dato sea constante,
žaplicado a otras estructuras, como listas enlazadas , etc. , el tiempo de acceso a un elemento no es constante, depende de la posición del elemento.


Video del algoritmo shell short: 

Programa en C++: 

include <iostream.h>

void main (void)

{

int a[15];

int n, inc, i, j, tmp;

cout <<"De cuantos elementos es el arreglo? ";

cin >> n;

for (i=1; i<=n; i++)

{

cout <<"Introduce el elemento " <<i<<" : ";

cin >> a[i];

}

 

nc = n/2;

while (inc > 0)

{

for (i = inc +1; i<=n; i++)

{

tmp = a[i];

j=i;

while ( (j-inc) > 0 )

{

if (tmp < a[j-inc])

{

a[j]=a[j-inc];

j=j-inc;

}

else

break;

} // fin del while //

a[j]=tmp;

} // fin del for //

inc = inc/2;

} // fin del while //

cout <<endl;

for (i=1; i<=n; i++)

cout << a[i] <<endl;

} // fin de shell sort //