Ordenamiento 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.

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 //