MergeSort

Algoritmo de búsqueda de un elemento en un Vector mediante Merge-Sort. El método es Divide y Vence, y está realizado en C.

#include <cstdlib>
#include <iostream>
#define max 100
using namespace std;
void mezclar(int arreglo1[], int n1, int arreglo2[], int n2, int arreglo3[])
{
    int x1=0, x2=0, x3=0;

    while (x1<n1 && x2<n2) {
        if (arreglo1[x1]<arreglo2[x2]) {
            arreglo3[x3] = arreglo1[x1];
            x1++;
        } else {
            arreglo3[x3] = arreglo2[x2];
            x2++;
        }
        x3++;
    }
    while (x1<n1) {
        arreglo3[x3] = arreglo1[x1];
        x1++;
        x3++;
    }
    while (x2<n2) {
        arreglo3[x3] = arreglo2[x2];
        x2++;
        x3++;
    }
}

void mezcla(int vector[], int n)
{
    int *vector1, *vector2, n1, n2,x,y;
    if (n>1)
    {
        if (n%2 == 0)
            n1=n2=(int) n / 2;
        else
        {
            n1=(int) n / 2;n2=n1+1;
        }
        vector1=(int *) malloc(sizeof(int)*n1);
        vector2=(int *) malloc(sizeof(int)*n2);
        for(x=0;x<n1;x++)
            vector1[x]=vector[x];
        for(y=0;y<n2;x++,y++)
            vector2[y]=vector[x];
        mezcla(vector1, n1);
        mezcla(vector2,n2);
        mezclar(vector1, n1, vector2, n2, vector);
        free(vector1);
        free(vector2);
    }     
}
void printlist(int vector[],int n)
{
   int i;
   for(i=0;i<n;i++){
      cout<< vector[i]<<"\t";
      }
      cout<<endl<<endl;
}

int main(){
    int i, vector[max];
    int n;
   
    cout<<"Introduce el número de elementos del vector :"<<endl;
    cin>>n;
  
    for(i=0;i<n;i++)
    {
       cout<<" vector["<<i+1<<"]=";
       cin>>vector[i];
    }
  
    cout<<"El vector introducido es:"<<endl;
    printlist(vector,n);
  
    mezcla(vector,n);

    cout<<"El vector ordenado mediante el método de mezclar es:"<<endl;
    printlist(vector,n); //imprimir la lista
   
    system("pause");
    return 0;
}

QuickSort

Algoritmo para ordenar un vector. Método mediante Divide y Vence realizado en C. Espero que sea útil!!

#include <cstdlib>
#include <iostream>
#define max 100
using namespace std;
void swap(int *x,int *y)
{
   int temp;
   temp = *x;
   *x = *y;
   *y = temp;
}
int pivote(int i,int j )
{
   return((i+j) /2);
}
void quicksort(int list[],int m,int n)
{
   int key,i,j,k;
   if( m < n)
   {
      k = pivote(m,n);
      swap(&list[m],&list[k]);
      key = list[m];
      i = m+1;
      j = n;
      while(i <= j)
      {
         while((i <= n) && (list[i] <= key))
                i++;
         while((j >= m) && (list[j] > key))
                j--;
         if( i < j)
                swap(&list[i],&list[j]);
      }
      swap(&list[m],&list[j]); //Intercambiar elementos
      quicksort(list,m,j-1); //Llamadas recursivas para ordenar la primera mitad
      quicksort(list,j+1,n); //Llamada ercursiva para ordenar la segunda mitad
   }
}
void printlist(int list[],int n)
{
   int i;
   for(i=0;i<n;i++){
      cout<< list[i]<<"\t";
      }
      cout<<endl<<endl;
}
int main(int argc, char *argv[])
{
   int n;
   int list[max];
   int i = 0;
   cout<<"Introduce el número de elementos del vector :"<<endl;
   cin>>n;
  
   for(i=0;i<n;i++)
   {
       cout<<" list["<<i+1<<"]=";
       cin>>list[i];
   }
   cout<<"El vector introducido es:"<<endl;
   printlist(list,n);
  
 
   quicksort(list,0,n-1); //ordenar la lista
  
   cout<<"El vector ordenado mediante el método quicksort es:"<<endl;
   printlist(list,n); //imprimir la lista
   system ("pause");
   return EXIT_SUCCESS;
}

Búsqueda en un vector con coste Logarítmico O(log n)

Hoy os dejo un algorítmico el cual realiza una búsqueda en función de la posición de un vector con coste logarítmico. Empleando el sistema de Divide y Vence y en lenguaje de programación C. Espero que os sea útil!

#include <stdio.h>
#include <stdlib.h>

int Selec(int a[], int k, int n);
int main(int argc, char *argv[]){
    int i,elem,array[12]={47,23,2,7,1,31,15,20,9,5,16,17},d;
    printf("\n PROBLEMA DE SELECCION DE ELEMENTOS \n");
    printf("\n");
    for (i=0;i<12;i++){
        printf(" %d",array[i]);
        }
    printf("\n\n Introduzca la posicion k: ");
    scanf("%d",&elem);
    printf(" \n Se ha seleccionado la posicion %d\n",elem);
    d=Selec(array,elem,12);
    printf("\n En el vector ordenado en la posicion %d esta %d",elem,d);
    printf("\n");
    system("PAUSE");
    return 1;
}

int Selec(int a[], int k, int n){
    int pri,u,v;
    pri=a[0];
    u=0;v=0;
    int m;
    int i;
    for(i=0;i<n;i++){
                     if (a[i]<pri) u++;
                     if (a[i]<=pri) v++;
    }
    if (k<=u){
       int j=0;
       int t[n];
       int h;
       for(h=0;h<n;h++){
                        if(a[h]<pri)
                                    t[j++]=a[h];
                                    }
                        return (Selec(t,k,j));
                        }
       if (k<=v){ return pri;}
       else {
            int t[n],j=0;
            int g;
            for(g=0;g<n;g++){
                             if(a[g]>pri) t[j++]=a[g];
                             }
            return (Selec(t,k-v,j));
            }
}

Búsqueda Binaria y Terciaria en C

Para empezar, os muestro algo sencillito como es realizar una búsqueda binaria y terciaria en un vector por el método de Divide y Vence, el lenguaje empleado para este algoritmo es C. Espero que os sea útil! Como veréis primero hay que introducir el vector y ordenarlo, después en el main comentas el método de búsqueda que quieras emplear y listo!

#include <cstdlib>
#include <iostream>
#define max 100
using namespace std;
void introducirVector(float A[max],int n)
{
 int i;
  for(i=0;i<n;i++)
  {
       cout<<" A["<<i+1<<"]=";
       cin>>A[i];
  }
  cout<<endl;
}
void mostrarVector(float V[max],int n)
{
   int i;
    for(i=0;i<n;i++)
   {
        cout<< V[i]<<"\t";      
   }
   cout<<endl<<endl;
}
//Con este método ordenaremos el vector previamente a la búsqueda//
void ordenarSeleccion(float V[max],int n)
{
   int i,j,k;
   float temp;
    for(i=0;i<n-1;i++)
    {        k=i;         
             temp=V[i];
             for(j=i+1;j<n;j++)
             {   if(V[j]<temp) //Intercambio
                   {  k=j;
                      temp=V[j];
                    }     
             }
             V[k]=V[i] ;
             V[i]=temp;                  
    }
}
//Busqueda de un elemento en el vector//
int  busquedaBinaria(float V[max],int n ,int dato)
{
  int mitad,izq,der;
  izq=0;
  der=n-1;
  while(izq<=der)
    {mitad=(izq+der)/2;//elemento central del vector para dividirlo
    if(dato>V[mitad])        
     izq=mitad+1;
    else if(dato<V[mitad])
    der=mitad-1;
    else return mitad;
     }
  return -1;//En caso de que no se encuentre
}
int  busquedaTerciaria(float V[max],int prim, int n ,int dato)
{
     int izq,der,nterc;
     izq=prim;
     der=n;
     cout<<"0izq vale"<<izq<<endl;
     cout<<"0der vale"<<der<<endl;
     if (izq>=der){
        V[der]=dato;
        return der;
     }
     nterc=(der-izq+1)/3;//dividimos por un tercio
     cout<<"nterc vale"<<nterc<<endl;
     cout<<"dato vale"<<dato<<endl;
     system("pause");
     if(dato==V[nterc]){
      return nterc; }
       else if(dato<V[nterc]){ 
         cout<<"1izq vale"<<izq<<endl;
         cout<<"1der vale"<<der<<endl;         
         busquedaTerciaria(V,izq,nterc,dato);
         }
       else if(dato==V[der-nterc])
         return der-nterc;
       else if(dato<V[der-nterc]){   
         cout<<"2izq vale"<<izq<<endl;
         cout<<"2der vale"<<der<<endl;
         busquedaTerciaria(V,izq+nterc+1,der-nterc-1,dato);
         }
         else
           cout<<"3izq vale"<<izq<<endl;
           cout<<"3der vale"<<der<<endl;
           busquedaTerciaria(V,der-nterc+1,der,dato);
           }
int main(int argc, char *argv[])
{
     float A[max];
     int n,p=0,dato;
     int pos;
     cout<<"Introduce el número de elementos del vector :";
     cin>>n;
     introducirVector(A,n);
     cout<<"El vector introducido es:"<<endl;
     mostrarVector(A,n);
     ordenarSeleccion(A,n);
     cout<<"El vector ordenado:"<<endl;
     mostrarVector(A,n);
     cout<<"Introduzca el número a buscar:";
     cin>>dato;
     pos=busquedaTerciaria(A,1,n,dato);
     //pos=busquedaBinaria(A,n,dato);
     {  if(pos ==-1)
           cout<<"el dato no esta en el vector"<<endl;
        else
        cout<<"El número se encontro en la posicion:"<<pos +1<<endl;
     }
    system("PAUSE");
   return EXIT_SUCCESS;
}

Presentación

Para empezar el Blog, comentar que soy un Ingeniero que me dedico a programar, como muchos de vosotros seréis o acabaréis siendo jeje. Iré colgando algoritmos en función del tiempo del que disponga y los conocimientos que tenga. Si alguno necesita alguna ayuda simplemente dejar vuestro comentario y cuando pueda contestaré. Un saludo

PD.: La mayoría de los algoritmos están hechos por mi, por lo que seguramente sean mejorables. Por lo que podéis comentar las mejoras y se mira.