Ordenar enteros usando el algoritmo de mezcla

Cerrando el ciclo de los algoritmos de ordenación, presento un programa que he adaptado de esta referencia:

http://es.wikipedia.org/wiki/Ordenamiento_por_mezcla

y que usa el algoritmo de mezcla. El código es el siguiente:

#include <iostream>

using namespace std;

void mezclar(int arreglo1[], int n1, int arreglo2[], int n2, int arreglo3[]);

void mezcla(int vector[], int n);
 
int main(){

    int i, vector[] = {2, 3, 5, 7, 2, 6, 1, 5, 8, 3, 2};

	cout << "Lista desordenada\n";
 
    for(i = 0; i < 11; i++)

		cout << vector[i] << " ";
 
    mezcla(vector, 11);

	cout << "\n";
 
	cout << "Lista ordenada\n";
 
    for(i=0;i<11;i++)

		cout << vector[i] << " ";

	cout << "\n";
 
    return 0;

}

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 = new int [n1];
 
    vector2 = new 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);

		delete vector1;

        delete vector2;

    } 	 
}

Después de grabado como mezcla.cpp, en Linux se compila y ejecuta con:

g++ mezcla.cpp -o mezcla [Enter]
./mezcla [Enter]

y esta es la salida por pantalla:

Lista desordenada
2 3 5 7 2 6 1 5 8 3 2 
Lista ordenada
1 2 2 2 3 3 5 5 6 7 8 

Para fines de comparación, ya tendríamos funcionando programas con los siguientes algoritmos de ordenamiento:

Burbuja
Inserción
Introsort (QuickSort+Heapsort)
Mezcla

Este es el directorio comprimido del proyecto: MEZCLA_C++.zip

Esta entrada fue publicada en Código C++ y etiquetada , . Guarda el enlace permanente.

Responder

Por favor, inicia sesión con uno de estos métodos para publicar tu comentario:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s