Mostrando entradas con la etiqueta Shell Sort. Mostrar todas las entradas
Mostrando entradas con la etiqueta Shell Sort. Mostrar todas las entradas

martes, 26 de noviembre de 2013

Método de Ordenamiento Shell Sort en C++

Hola amig@s esta vez les traigo otro método de ordenación interna como lo es el Shell sort este método es una generalización del ordenamiento por inserción, teniendo en cuenta dos observaciones:

1- El ordenamiento por inserción es eficiente si la entrada está "casi ordenada".
2- 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.





Codigo:

ShellSort.cpp:


#include "ShellSort.h" void main(){ ShellSort SS; int n; do{cout<<"Cuantos elementos desea ingresar: ";cin>>n;}while(n<1||n>100); for(int i=0;i<n;i++){ cout<<endl<<"Dato["<<i+1<<"]: ";cin>>SS.vector[i]; } system("cls"); cout<<endl<<endl<<"Vector original:"<<endl<<endl; for(int i=0;i<n;i++){ cout<<SS.vector[i]<<" "; } SS.shellSort(SS.vector,n); cout<<endl<<endl<<"Vector Ordenado Con Metodo de ShellSort:"<<endl<<endl; for(int i=0;i<n;i++){ cout<<SS.vector[i]<<" "; } system("pause>null"); }


ShellSort.h:


#include <iostream> #include <windows.h> using namespace std; class ShellSort{ public: int vector[100],temp,inc,i,j; void shellSort(int[], int ); void mostrar(int[], int ); }; void ShellSort::shellSort(int V[], int N){ for(inc = 1 ; inc<N;inc=inc*3+1); while (inc > 0){ for ( i=inc; i < N; i++){ j = i; temp = V[i]; while ((j >= inc) && (V[j-inc] > temp)){ V[j] = V[j - inc]; j = j - inc; } V[j] = temp; } inc/= 2; } } void ShellSort::mostrar(int V[],int N){ for(int i=0;i<N;i++){ cout<<V[i]<<" "; } }

Descarga el código fuente desde aquí.