C++ の質問です

質問

vector a の中に 1 4 9 16 vector b の中に 4 7 9 9 11 が入っていて

新しい vector c の中に 1 4 4 7 9 9 9 11 16 のように小さい順に並べたいのですが、

どのようなforloop をかいたら良いのでしょうか？？ アドバイスください。。

つなげることしか出来ないです。。。

vector<int> mergeSorted(const vector<int>& a, const vector<int>& b)
{
int n = a.size();
int m = b.size();
vector<int> c(n + m);
int i;

for (i = 0; i < n; i++)
c[i] = a[i];

for (i = 0; i < m; i++)
c[n + i] = b[i];

return c;

}

sort() を使ってはいけないという条件です。 なにか、アイディアありましたら、お願いいたします、、

回答No.4

Tacosan

stable_sort でいいなら qsort でもいいような気がする＞#3.

回答No.3

jacta

#2さんのやり方で十分だと思いますが...

> sort() を使ってはいけないという条件です。

確かに連結してからソートする方がわかりやすいですからね。
sort関数を使ってはいけないのであれば、stable_sort関数ならOKということでしょうか？

回答No.2

Tacosan

#include <algorithm>
#include <iterator>
を前提に
std::merge(a.begin(), a.end(), b.begin(), b.end(), std::back_inserter(c));
とか?

回答No.1

hanabutako

典型的なマージソートのマージする部分のコードですよね。
http://ja.wikipedia.org/wiki/%E3%83%9E%E3%83%BC%E3%82%B8%E3%82%BD%E3%83%BC%E3%83%88

vector<int> mergeSorted(const vector<int>& a, const vector<int>& b)
{
vector<int> c;
size_t ai = 0, bi = 0;
c.reserve(a.size() + b.size());

while (ai < a.size() && bi < b.size()) {
if (a[ai] < b[bi]) {
c.push_back(a[ai++]);
} else {
c.push_back(b[bi++]);
}
}

while (ai < a.size()) {
c.push_back(a[ai++]);
}

while (bi < b.size()) {
c.push_back(b[bi++]);
}

return c;
}

最初のwhileで小さいものから、どちらかのvectorが使いきるまで小さい方の要素をとってcに追加し、後のほうで残ったやつを後ろにつなげます。
使いきった方は空なのがわかっていますし、どちらが空になったかを調べるのも面倒なので、両方共で残ったのがあったら追加するということにしています。