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ándolos.El 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.
Métodos de Ordenamiento ShellSort en C++ - Código Fuente
#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];
}
}
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;
}
}
0 comments:
Publicar un comentario