Curso 2024/2025
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
.
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; }
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; }
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; }
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; }
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; }