Metodo de Ordenacion Shaker Sort en C++

Hola amig@s en esta ocasión y continuando con los métodos de ordenación les mostare el Shaker sort es también, y mejor, conocido como Cocktail Sort y en castellano como Burbuja Didireccional o Sacudida es la mejora del método de burbuja en el que el proceso se realiza desde la primera posición a la última de la disposición en la dirección opuesta, impidiendo así artículos más pequeños se lleva más tiempo para "subir" a las primeras posiciones.

Imagen:

Código:

ShakerSort.cpp:

#include "ShakerSort.h"
void main(){
 ShakerSort SK;
 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>>SK.vector[i];
 }
 system("cls");
 cout<<endl<<endl<<"Vector original:"<<endl<<endl;
 for(int i=0;i<n;i++){
  cout<<SK.vector[i]<<" ";
 }
 SK.shakerSort(SK.vector,n);
 cout<<endl<<endl<<"Vector Ordenado Con El Metodo Shaker Sort (Sacudida):"<<endl<<endl;
 for(int i=0;i<n;i++){
  cout<<SK.vector[i]<<" ";
 }
 system("pause>null");
}

ShakerSort.h:

#include <iostream>
#include <windows.h>
using namespace std;
class ShakerSort{
public:
 int vector[100];
 void shakerSort(int[] ,int );
};
void ShakerSort::shakerSort(int v[],int N){
 int i = 0 , izq = 1 , der = N-1 , k = N-1 , aux = 0;
 while( der >= izq ){      
  for( i = der ; i>= izq ; i-- )          
   if( v[i-1] > v[i]){
    aux = v[i-1];      
    v[i-1]=v[i];
    v[i]=aux;
    k=i;
   }
   izq = k + 1;
   for( i = izq ; i <= der ; i++)
    if( v[i-1] > v[i] ){
     aux = v[i-1];
     v[i-1]=v[i];
     v[i]=aux;
     k=i;
   }
    der = k-1;
 }
}

Descarga el código fuente desde aquí.

Método de Ordenación Inserción Binaria en C++

Hola amig@s aquí esta otro de los métodos de ordenación interna en esta ocasión se trata de Inserción Binaria este método es una mejora del método de ordenación por  inserción directa.

La mejora consiste en realizar una búsqueda binaria en lugar de una  búsqueda secuencial,para insertar el elemento en la posición que le corresponde.

Imagen:

Codigo:

InsercionBinaria.cpp:

#include "InsercionBinaria.h"
void main(){
 InsercionBinaria IB;
 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>>IB.vector[i];
 }
 system("cls");
 cout<<endl<<endl<<"Vector original:"<<endl<<endl;
 for(int i=0;i<n;i++){
  cout<<IB.vector[i]<<" ";
 }
 IB.insercionBinaria(IB.vector,n);
 cout<<endl<<endl<<"Vector Ordenado Con Metodo de Insercion Binaria:"<<endl<<endl;
 for(int i=0;i<n;i++){
  cout<<IB.vector[i]<<" ";
 }
 system("pause>null");
}

InsercionBinaria.h

#include <iostream>
#include <windows.h>
using namespace std;
class InsercionBinaria{
public:
 int vector[100],i,j,aux,izq,der,m;
 void insercionBinaria(int[], int );
 void mostrar(int[], int );
};

void InsercionBinaria::insercionBinaria(int V[],int N){
 for(i=1;i<N;i++){
  aux = V[i];
  izq=0;
  der=i-1;
  while(izq<=der){
   m=((izq+der)/2);
   if (aux<V[m])
    der=m-1;
   else
    izq=m+1;              
  }
  j=i-1;
  while(j>=izq){
   V[j+1]=V[j];
   j=j-1;
  }
  V[izq]=aux;
 }  
}

void InsercionBinaria::mostrar(int V[],int N){
 for(int i=0;i<N;i++){
  cout<<V[i]<<" ";
 }
}

descarga el código fuente desde aquí.

Metodo de Ordenacion por Insercion Directa en C++

Hola amig@s en esta ocasión les traigo otro método de ordenación interna como lo es el de Inserción Directa es un algoritmo relativamente sencillo y se comporta razonablemente bien en gran cantidad de situaciones.

 Se basa en intentar construir una lista ordenada en el interior del array a ordenar.

 De estos tres algoritmos es el que mejor resultado da a efectos prácticos. Realiza una cantidad de comparaciones bastante equilibrada con respecto a los intercambios, y tiene un par de características que lo hacen aventajar a los otros dos en la mayor parte de las situaciones.

 Este algoritmo se basa en hacer comparaciones, así que para que realice su trabajo de ordenación son imprescindibles dos cosas: un array o estructura similar de elementos comparables y un criterio claro de comparación, tal que dados dos elementos nos diga si están en orden o no.

Imagen:

Código:

InsercionDirecta.cpp:

#include "InsercionDirecta.h"
void main(){
 InsercionDirecta ID;
 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>>ID.vector[i];
 }
 system("cls");
 cout<<endl<<endl<<"Vector original:"<<endl<<endl;
 for(int i=0;i<n;i++){
  cout<<ID.vector[i]<<" ";
 }
 ID.insercionDirecta(ID.vector,n);
 cout<<endl<<endl<<"Vector Ordenado Con Metodo de Insercion Directa:"<<endl<<endl;
 for(int i=0;i<n;i++){
  cout<<ID.vector[i]<<" ";
 }
 system("pause>null");
}

InsercionDirecta.h

#include <iostream>
#include <windows.h>
using namespace std;
class InsercionDirecta{
public:
 int vector[100],i,j;
 void insercionDirecta(int[], int );
 void mostrar(int[], int );
};

void InsercionDirecta::insercionDirecta(int V[],int N){
      int i,j,v;
      for (i = 1; i < N; i++){
    v = V[i];
    j = i - 1;
    while (j >= 0 && V[j] > v){
      V[j + 1] = V[j];
      j--;
    }   
    V[j + 1] = v;
   }   
}

void InsercionDirecta::mostrar(int V[],int N){
 for(int i=0;i<N;i++){
  cout<<V[i]<<" ";
 }
}

Descarga el código fuente desde aquí.

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