Algoritmo de ordenamiento Shell
El método se denomina así en honor de su inventor Donald Shell. Su implementación
original, requiere O(n2) comparaciones e intercambios en el peor caso, aunque un cambio
menor presentado en el libro de V. Pratt produce una implementación con un rendimiento
de O(n log2 n) en el peor caso. Esto es mejor que las O(n2) comparaciones requeridas por
algoritmos simples pero peor que el óptimo O(n log n).
El Shell sort es una generalización del ordenamiento por inserción, teniendo en cuenta dos
observaciones: El ordenamiento por inserción es eficiente si la entrada está "casi ordenada".
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.
Descripción
El algoritmo Shell es una mejora de la ordenación por inserción, donde se van comparando
elementos distantes, al tiempo que se los intercambian si corresponde. A medida que se
aumentan los pasos, el tamaño de los saltos disminuye; por esto mismo, es útil tanto como
si los datos desordenados se encuentran cercanos, o lejanos.
Es bastante adecuado para ordenar listas de tamaño moderado, debido a que su velocidad es
aceptable y su codificación es bastante sencilla. Su velocidad depende de la secuencia de
valores con los cuales trabaja, ordená[Link] siguiente ejemplo muestra el proceso de
forma gráfica:
Considerando 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
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 sólo unas
pocas comparaciones e intercambios.
#include<iostream>
#include<conio.h>
using namespace std;
int Arreglo[100];
void LeerArreglo(int Numero);
void EscribeArreglo(int Numero);
void Shell(int Numero);
int main(){
int Num;
cout<<"Ingrese dimension del arreglo : ";
cin>>Num;
LeerArreglo(Num);
Shell(Num);
cout<<endl;
EscribeArreglo(Num);
return 0;
}
void LeerArreglo(int Numero){
int i;
for(i=1;i<=Numero;i++)
{
cout<<"Arreglo["<<i<<"]=";
cin>>Arreglo[i];
}
}
void EscribeArreglo(int Numero){
int i;
cout<<"elementos ordenados por metodo Shell sort"<<endl;
for(i=1;i<=Numero;i++)
{
cout<<"\t"<<Arreglo[i];
}
cout<<endl;
system("pause");
}
void Shell(int Numero){
int i,j,k,incremento,aux;
incremento=Numero/2;
while(incremento>0){
for(i=incremento+1;i<=Numero;i++){
j=i-incremento;
while(j>0){
if(Arreglo[j]>=Arreglo[j+incremento]){
aux = Arreglo[j];
Arreglo[j] = Arreglo[j+incremento];
Arreglo[j+incremento] = aux;
}
else{
j=0;
}
j=j-incremento;
}
}
incremento=incremento/2;
}
cout<<endl;
