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

Metodo de Burbuja (Bubble Sort) en C++

Hola amig@s esta ves les traigo el Método de Ordenación de Burbuja o Bubble Sort (en ingles) este método funciona revisando cada elemento de la lista que va a ser ordenada con el siguiente, intercambiándolos de posición si están en el orden equivocado. Es necesario revisar varias veces toda la lista hasta que no se necesiten más intercambios, lo cual significa que la lista está ordenada. Este algoritmo obtiene su nombre de la forma con la que suben por la lista los elementos durante los intercambios, como si fueran pequeñas "burbujas". También es conocido como el método del intercambio directo. Dado que solo usa comparaciones para operar elementos, se lo considera un algoritmo de comparación, siendo el más sencillo de implementar.

Imagen:

Código:

BubbleSort.cpp:

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

BubbleSort.h:

#include <iostream>
#include <windows.h>
using namespace std;
class BubbleSort{
public:
 int vector[100],tmp;
 void bubbleSort(int[],int);
 void mostrar(int[],int);
};
void BubbleSort::bubbleSort(int V[],int N){
 for(int i=0;i<N;i++){ 
        for(int j=i+1;j<N;j++){ 
            if(V[i]>V[j]){ 
                tmp=V[i]; 
                V[i]=V[j]; 
                V[j]=tmp; 
            } 
        } 
    } 
}
void BubbleSort::mostrar(int V[],int N){
 for(int i=0;i<N;i++){
  cout<<V[i]<<" ";
 }
}

Descarga el código fuente desde aquí.