elhacker.net cabecera Bienvenido(a), Visitante. Por favor Ingresar o Registrarse
¿Perdiste tu email de activación?.

 

 


Tema destacado: Únete al Grupo Steam elhacker.NET


+  Foro de elhacker.net
|-+  Programación
| |-+  Programación C/C++ (Moderadores: Eternal Idol, Littlehorse, K-YreX)
| | |-+  Merge sort en C++
0 Usuarios y 1 Visitante están viendo este tema.
Páginas: [1] Ir Abajo Respuesta Imprimir
Autor Tema: Merge sort en C++  (Leído 1,859 veces)
BitsPuke

Desconectado Desconectado

Mensajes: 5


Ver Perfil
Merge sort en C++
« en: 7 Diciembre 2014, 13:14 pm »

Buenas tengo que implementar este algoritmo para ordenar un vector en una practica de C++ tanto en forma recursiva y como iterativa. La recursiva la he hecho sin problemas pero llevo desde ayer dandole vueltas a la iterativa y no consigo hallar manera de implementarla en C++. Estoy atascado.

Aqui os dejo un gif sacado de wikipedia de lo que hace el algoritmo y mi codigo:


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

Funcion main
Código
  1. #include "divideyvenceras.hpp"
  2.  
  3. main (){
  4.  
  5.  vector <int> vectorDesordenado;
  6.  
  7.  CrearVector(vectorDesordenado);
  8.  
  9.  OrdenarPorFusion(vectorDesordenado, true);
  10.  
  11.  MostrarVector(vectorDesordenado);
  12.  
  13. }

Resto del programa
Código
  1. #include <iostream>
  2. #include <cstdlib>
  3. #include <vector>
  4. using namespace std;
  5. #define INFINITO 2147483647
  6.  
  7. void MostrarVector (vector <int> vecT){
  8.  for (int i=0;i<vecT.size();i++)
  9.    cout << "[ " << vecT[i] << " ]";  
  10.  cout << endl;
  11. }
  12.  
  13. void Fusionar (vector <int> &vecT, vector<int> vecU, vector <int> vecV){
  14.  int i=0,j=0,m, n;
  15.  m=vecU.size();
  16.  n=vecV.size();
  17.  vecU.push_back(INFINITO);
  18.  vecV.push_back(INFINITO);
  19.  
  20.  for (int k=0; k<m+n; k++){
  21.    if (vecU[i]<vecV[j]){
  22.      vecT[k]=vecU[i];
  23.      i++;
  24.    }
  25.    else{
  26.      vecT[k]=vecV[j];
  27.      j++;      
  28.    }      
  29.  }
  30.  
  31. }
  32.  
  33. void OrdenarPorFusion (vector <int> &vecT, bool verbose){
  34.  int n=vecT.size();
  35.  if (verbose) MostrarVector (vecT);
  36.  if (n>1){ //Si el tamaño es lo suficientemente pequeño (?)
  37.    vector <int> vecU;
  38.    vector <int> vecV;
  39.    //Dividir vector en 2
  40.    for (int i=0; i<n; i++){
  41.      if (i<n/2)
  42. vecU.push_back(vecT[i]);
  43.      else vecV.push_back(vecT[i]);      
  44.    }
  45.    //Recursivo    
  46.    OrdenarPorFusion(vecU, verbose);
  47.    OrdenarPorFusion(vecV, verbose);
  48.    Fusionar(vecT,vecU,vecV);
  49.  }
  50.  
  51. }
  52.  
  53. void CrearVector (vector <int> &vecT){
  54.  int n;
  55.  cout << "Tamaño del vector: ";
  56.  cin >> n;  
  57.  
  58.  srand (time(NULL)); //Semilla a 0
  59.  for (int i=0;i<n;i++)
  60.    vecT.push_back(rand()%10); //Numero pseudoaleatorio entre 0 y 10    
  61. }

Me pueden dar alguna pista de como hacer la version iterativa?
Muchas gracias!


En línea

Páginas: [1] Ir Arriba Respuesta Imprimir 

Ir a:  

WAP2 - Aviso Legal - Powered by SMF 1.1.21 | SMF © 2006-2008, Simple Machines