Algoritmos y Estructuras de Datos - VJ1215

Solución del ejercicio 12.a del tema 1

A continuación puedes encontrar 5 implementaciones válidas del mismo algoritmo. Todas ellas tienen coste temporal en el peor caso O(n), siendo n la cantidad total de elementos en los dos vectores dados. Una forma simple de analizar su coste temporal es fijarse en cómo depende de cuántas veces se incrementa la variable pos3.

Versión 1

vector<float> mezclar(const vector<float> & v1, const vector<float> & v2) {

   vector<float> v3(v1.size() + v2.size());

   int pos1 = 0, pos2 = 0, pos3 = 0;

   while (pos1 < v1.size() && pos2 < v2.size())
      if (v1[pos1] <= v2[pos2])
	 v3[pos3++] = v1[pos1++];
      else
	 v3[pos3++] = v2[pos2++];

   while (pos1 < v1.size())
      v3[pos3++] = v1[pos1++];

   while (pos2 < v2.size())
      v3[pos3++] = v2[pos2++];

   return v3;

}

Versión 2

vector<float> mezclar(const vector<float> & v1, const vector<float> & v2) {

   vector<float> v3(v1.size() + v2.size());

   int pos1 = 0, pos2 = 0, pos3 = 0;

   while (pos1 < v1.size() || pos2 < v2.size())
      if (pos2 == v2.size())
	 v3[pos3++] = v1[pos1++];
      else if (pos1 == v1.size())
	 v3[pos3++] = v2[pos2++];
      else if (v1[pos1] <= v2[pos2])
	 v3[pos3++] = v1[pos1++];
      else
	 v3[pos3++] = v2[pos2++];


   return v3;

}

Versión 3

vector<float> mezclar(const vector<float> & v1, const vector<float> & v2) {

   vector<float> v3(v1.size() + v2.size());

   int pos1 = 0, pos2 = 0, pos3 = 0;

   while (pos1 < v1.size() || pos2 < v2.size())
      if (pos2 == v2.size() || (pos1 < v1.size() && v1[pos1] <= v2[pos2]))
	 v3[pos3++] = v1[pos1++];
      else
	 v3[pos3++] = v2[pos2++];

   return v3;

}

Versión 4

vector<float> mezclar(const vector<float> & v1, const vector<float> & v2) {

   vector<float> v3(v1.size() + v2.size());

   int pos1 = 0, pos2 = 0, pos3 = 0;

   while (pos1 < v1.size())
      if (pos2 < v2.size() && v2[pos2] <= v1[pos1])
	 v3[pos3++] = v2[pos2++];
      else
	 v3[pos3++] = v1[pos1++];

   while(pos2 < v2.size())
      v3[pos3++] = v2[pos2++];

   return v3;

}

Versión 5

vector<float> mezclar(const vector<float> & v1, const vector<float> & v2) {

   vector<float> v3(v1.size() + v2.size());

   int pos1 = 0, pos2 = 0;

   for (int pos3 = 0; pos3 < v3.size(); pos3++)
      if (pos2 == v2.size() || (pos1 < v1.size() && v1[pos1] <= v2[pos2]))
	 v3[pos3] = v1[pos1++];
      else
	 v3[pos3] = v2[pos2++];

   return v3;

}