Métodos de Ordenamiento MergeSort en C++ - Código Fuente

Definición

Consiste en dividir el problema a resolver en subproblemas del mismo tipo que a su vez se dividirán, mientras no sean suficientemente pequeños o triviales.

Pasos

1: Ordenar una secuencia S de elementos:
Si S tiene uno o ningún elemento, está ordenada
Si S tiene al menos dos elementos se divide en dos secuencias S1 y S2, S1 conteniendo los primeros n/2, y S2 los restantes.
2: Ordenar S1 y S2, aplicando recursivamente este procedimiento.
Mezclar S1 y S2 ordenadamente en S
Mezclar dos secuencias ordenadas S1 y S2 en S:
Se tienen referencias al principio de cada una de las secuencias a mezclar (S1 y S2).
Mientras en alguna secuencia queden elementos, se inserta en la secuencia resultante (S) el menor de los elementos referenciados y se avanza esa referencia una posición.

Complejidad del algoritmo
Para ordenar un arreglo de tamaño n se ordenan 2 arreglos de tamaño n/2, de aquí el 2T(n/2), y luego se consume O(n) en realizar la mezcla. Resolviendo la ecuación recurrente tenemos que T(n) = O(n log n).

Propiedades

1. Es Estable.
2. Memoria Auxiliar O(n).
3. No ordena en el lugar.
4. Es O(n log n).

Métodos de Ordenamiento MergeSort en C++ - Código Fuente

DESCARGA | MEGA

#include<iostream> #include<conio.h> using namespace std; int a[50]; void merge(int,int,int); void merge_sort(int izquierda,int derecha){ int medio; if(izquierda<derecha){ medio=(izquierda+derecha)/2; merge_sort(izquierda,medio); merge_sort(medio+1,derecha); merge(izquierda,medio,derecha); } } void merge(int izquierda,int medio,int derecha){ int h,i,j,b[50],k; h=izquierda; i=izquierda; j=medio+1; while((h<=medio)&&(j<=derecha)){ if(a[h]<=a[j]){ b[i]=a[h]; h++; } else { b[i]=a[j]; j++; } i++; } if(h>medio){ for(k=j;k<=derecha;k++){ b[i]=a[k]; i++; } } else { for(k=h;k<=medio;k++){ b[i]=a[k]; i++; } } for(k=izquierda;k<=derecha;k++){ a[k]=b[k]; } } int main(){ int num,i; cout<<" *******************************"<<endl; cout<<" PROGRAMA MERGE SORT "<<endl; cout<<" ****************************** "<<endl; cout<<endl<<endl; cout<<"INGRESE LA CANTIDAD DE ELEMENTOS"<<endl; cin>>num; cout<<endl; cout<<"LOS ELEMENTOS SON:"<<endl; for(i=1;i<=num;i++){ cin>>a[i] ; } merge_sort(1,num); cout<<endl; cout<<endl<<endl; cout<<"EL NUEVO ORDEN DE ELEMENTOS ES:"<<endl; for(i=1;i<=num;i++){ cout<<a[i]<<" "; } return 0; }

LEER MÁS

Métodos de Ordenamiento ShellSort en C++ - Código Fuente

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

DESCARGA | MEGA

#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; } }

LEER MÁS

Métodos de Ordenamiento ShakerSort en C++ - Código Fuente

Métodos de ordenamiento

Es la operación mediante la cual permite arreglar u organizar datos de una tabla o lista de una forma adecuada y principalmente secuencial teniendo en cuenta un  criterio de ordenamiento. El ordenamiento se puede realizar siempre que exista un valor como requisito en algún lugar o campo. El principal objetivo  de los métodos de ordenamiento, es que permita facilitar y agilizar la búsqueda de miembros o valores de un conjunto ordenado.

Cuando se habla de ordenamiento de datos significa mover los datos y dichas referencias, las cuales permitan una secuencia tal que represente un orden. dicho orden puede ser numérico, alfabético o incluso alfanumérico.

Los métodos de ordenamiento en el campo de estructura de datos son esenciales puesto que permiten almacenar información, recuperar información de una manera eficiente y coherente. El rol de los métodos de ordenamiento es ordenar una serie o grupo de datos, dichas acciones implican mover datos que queden en una secuencia la cual represente un orden.

Ordenación Shaker
El algoritmo de ordenación por el método Shaker, también conocido como "Cocktail" o "Sacudida" es una mejora del método de la burbuja en la cual el proceso se realiza tanto desde la primera posición a la última del arreglo como en sentido inverso, evitando así que los elementos más pequeños tarden un mayor tiempo
en "ascender" a las posiciones superiores.


Este método permite organizar, ordenamiento e intercambio directo de elementos del arreglo. Prácticamente la idea básica de este algoritmo consiste en intercambiar, mezclar. existen dos formas en que se pueda realizar este algoritmo cada pasada tiene 2 pasadas.En la primera pasada, es de derecha a izquierda se trasladan los elementos mas pequeños hacia la izquierda del arreglo (almacenando la posición del ultimo elemento intercambiado) en la segunda pasada de izquierda a derecha se trasladan los elementos mas grandes hacia la derecha del arreglo almacenando en otra variable la posición del ultimo elemento intercambiado. Este método de ordenamiento permite visualizar la forma, en la cual se puede organizar datos desordenados que al final serán ordenados de una forma secuencial.

 Métodos de Ordenamiento ShakerSort en C++ - Código Fuente 

DESCARGA | MEGA

#include<conio.h> #include<stdio.h> #include<stdlib.h> #include<iostream> using namespace std; int main(){ int i, k, Der, Izq, Aux, N, A[30]; cout<<"METODO DE ORDENAMIENTO - SHAKER SORT"<<endl; cout<<"Ingrese el tama�o del arreglo : "<<endl; cin>>N; k=N; Izq=2; Der=N; for(i=1;i<=N;i++){ cout<<"\tA["<<i<<"] : "; cin>>A[i]; } do{//inicio del ordenamiento for(i=Der;i>=Izq;i--){//derecha a izquierda if(A[i-1]>A[i]){ Aux=A[i-1]; A[i-1]=A[i]; A[i]=Aux; k=i; } } Izq=k+1; for(i=Izq;i<=Der;i++)//izquierda a derecha if(A[i-1]>A[i]){ Aux=A[i-1]; A[i-1]=A[i]; A[i]=Aux; k=i; } Der=k-1; }while(Izq<Der);//Fin del ordenamiento cout<<"\n\tArreglo Ordenado\n\t==================\n"; for(i=1;i<=N;i++) cout<<"\t"<<A[i]; cout<<endl<<"\t"; system("pause"); return 0; getch(); }

LEER MÁS