sábado, 30 de octubre de 2010

Ordenamiento por mezcla - MergeSort

MergeSort es un algoritmo de ordenamiento basado en la estrategia "divide y vencerás". Su orden asintótico es O(n log n), mucho mas eficiente que otros algoritmos de ordenamiento como burbuja, inserción o selección que son de orden cuadrático.

Básicamente MergeSort actúa de esta manera:
  1. Si la longitud del vector es 1 significa que ya esta ordenado y no hace nada.
  2. Sino, divide en vector por la mitad en dos subvectores.
  3. Ordena cada subvector de forma recursiva.
  4. Finalmente mezcla los subvectores ya ordenados uniéndolos en un solo vector ordenado.

Fig. 1 - Ejemplo de Mergesort.

Hay que destacar que la función que mezcla los subvectores (merge) es de tiempo lineal ya que solo tiene que sacar cada vez el mayor elemento de ambos subvectores (que ya están ordenados) y colocarlo consecutivamente en el vector resultante.

Ahora veamos una implementación del MergeSort en C++:

/*
Algoritmo de ordenamiento MergeSort.
Por: Alguien
Fecha: Domingo 09 de mayo del 2010
*/
#include <stdlib.h>
#include <stdio.h>

void mergesort(int *v, int i, int f);
void merge(int *v, int i, int m, int f);

int main() {
 int *v, n;
 printf("Ingrese N: ");
 scanf("%d", &n);
 
 v = new int[n];
 for(int i=0; i<n; i++) {
  printf("Elemento %d: ", i+1);
  scanf("%d", &v[i]);
 }
 
 mergesort(v, 0, n-1);
 
 for(int i=0; i<n; i++)
  printf("%d ", v[i]);
 
 return 0;
}

void mergesort(int *v, int i, int f) {
 if(i!=f) {
  int m = (i+f)/2;
  mergesort(v, i, m);
  mergesort(v, m+1, f);
  merge(v, i, m, f);
 }
}

void merge(int *v, int i, int m, int f) {
 int *aux = new int[m-i+1];
 for(int j=i; j<=m; j++)
  aux[j-i] = v[j];
 
 int c1=0, c2=m+1;
 for(int j=i; j<=f; j++) {
  if(aux[c1] < v[c2]) {
   v[j] = aux[c1++];
   if(c1==m-i+1)
    for(int k=c2; k<=f; k++)
     v[++j] = v[k];
  }
  else {
   v[j] = v[c2++];
   if(c2==f+1)
    for(int k=c1; k<=m-i; k++)
     v[++j] = aux[k];
  }
 } 
}

Saludos.

12 comentarios:

  1. hola tu podrias decir cual seria el O si el algoritmo esta previamente ordenado ?

    ResponderEliminar
  2. "n" es el tamaño del vector, o lo que es lo mismo el número de elementos.

    Un saludo

    ResponderEliminar
  3. que es f, m, c1 y c2 y en donde las declararon ?

    ResponderEliminar
  4. f y m se declaran como parametros de la funcion merge en la linea 40. c1 y c2 se declaran en la linea 45.

    i, m y f son indices (inicio, medio y fin) que se usan para dividir el vector "v" en dos subvectores (de i a m y de m+1 a f)

    c1 y c2 son variables auxiliares.

    ResponderEliminar
  5. haha de caasaualidad el hola es del ceti haha !!!!!!!!!
    me dicen al compilar que merge no esta declarado y esta declarado en la funcion ??

    ResponderEliminar
  6. Hola, el prototipo de la función merge se define en la linea 10 y el código de merge se implementa a partir de la 40. Verifica si incluiste el prototipo.

    En mi caso lo compilo así:

    # g++ mergesort.c -o mergesort

    ...y no me da problemas

    Un saludo.

    ResponderEliminar
  7. Hola,soy samuel necesito saber lo que hace cada función entre merge y mergesort de manera general

    ResponderEliminar
  8. "merge" recive por parámetro un vector "v" y tres indices: inicio "i", medio "m" y final "f". El vector v se divide en dos partes (subvectores) mediante estos indices: de v[i] a v[m] y de v[m+1] a v[f]. Se presupone que ambos subvectores estan ordenados independientemente. Lo que hace esta función es mezclar los subvectores tomando, cada vez, el menor elemento de ambos. De esta forma el resultado de la mezcla también estará ordenado.

    "mergesort" recibe tres parámetros: un vector "v" y dos indices inicio "i" y final "f". Esta función ordena el vector desde v[i] hasta v[f]. Para ello, primero parte el vector por la mitad calculando un indice "m" igual a la semisuma de los indices "i" y "f" y ordena ambas mitades de forma recursiva. Por ultimo mezcla las mitades (ya ordenadas) usando la funcion "merge". El caso frontera se dará cuando un subvector (mitad) sea unitario, es decir, contenga un único elemento, en ese caso los indicies de inicio y final son iguales y no es necesario ordenarlo.

    Un saludo.

    ResponderEliminar
  9. Quisiera sabe si tienes en diagrama de flujo el algoritmo de mergesort

    ResponderEliminar