C++ рекурсивная сортировка строк слиянием

Это вопрос домашнего задания, поэтому, хотя мне нужен пригодный для использования код, я действительно ищу понимание того, как решить эту проблему. У меня есть два отсортированных массива в порядке возрастания, которые мне нужно объединить в рекурсивной функции. Кажется, мне нужно установить сортирующую часть алгоритма сортировки слиянием. Требования заключаются в том, что рекурсивная функция может принимать только две отсортированные строки в качестве параметров и не может использовать глобальные или статические переменные.

Я думаю, что псевдокод:

  • если размер двух строк == 0, то вернуть результирующую строку.
  • сравните substr(0,1) каждой строки, чтобы увидеть, какая из них меньше, и добавьте ее в результирующую строку.
  • рекурсивно вызвать функцию с новыми параметрами, представляющими собой подстроку строки, к которой добавлен

Мои вопросы: как сохранить строку результата, если я не могу использовать статические переменные? Я видел код, в котором строка определяется как = оператору возврата рекурсивного вызова. Будет ли это работать в этом случае?

Второй вопрос заключается в том, как увеличить функцию. Мне нужно вызвать substr(1,size-1) после первой итерации, а затем увеличить ее без использования статических переменных.

Вот моя попытка решить уравнение СО статическими переменными (которые не разрешены):

static string result="";
static int vv=0;
static int ww=0;

if(v.size()==0 && w.size()==0)
    return result;
if(w.size()==0 || v.substr(0,1) <= w.substr(0,1)){ 
    result+=v.substr(0,1);
    vv++;
    return spliceSortedStrings( v.substr(vv,v.size()-vv) , w); 
    }
else if(v.size()==0 || w.substr(0,1) > v.substr(0,1)){
    result+=w.substr(0,1);
    ww++;
    return spliceSortedStrings( v , w.substr(ww,w.size()-ww));
    }

Я буду признателен за любое руководство.


c++ string recursion mergesort
person banana muffin    schedule 04.02.2014    source источник
comment
Извините, но я что-то пропустил. смысл этого упражнения в том, чтобы взять две строки отсортированных символов и рекурсивно объединить их в одну строку, где также сортируются результаты? И независимо от того, является ли это целью или нет, повторяющиеся вызовы substr() — это безумие, когда все, что вам нужно, это front() (при условии, что !empty() проверено). substr() дорого, так как каждый из них генерирует новую выделенную независимую строку.   -  person WhozCraig    schedule 04.02.2014
comment
Да, таковы были требования учений.   -  person banana muffin    schedule 04.02.2014
comment
Ok. Я опубликую что-нибудь, если вы думаете, что это поможет, хотя, похоже, у вас уже есть ответ, который вам нравится.   -  person WhozCraig    schedule 04.02.2014
comment
Ответ пользователя 1734710 был очень полезен.   -  person banana muffin    schedule 04.02.2014
comment
Я согласен, это причина, по которой я проголосовал за это.   -  person WhozCraig    schedule 04.02.2014

Ответы (1)


arrow_upward
1
arrow_downward

Как насчет этого:

std::string merge(std::string a, std::string b) {
    if (a.size() == 0) return b;
    if (b.size() == 0) return a;

    if (a.back() < b.back()) {
        std::string m = merge(a, b.substr(0, b.size()-1));
        return m + b.back();
    }
    else {
        std::string m = merge(a.substr(0, a.size()-1), b);
        return m + a.back();
    }
}

Правильность и прекращение должны быть очевидны, и я думаю, что они должны соответствовать ограничениям, которые вам даны. Но мне интересно, какой учитель поставит такую ​​задачу на C++, потому что приведенный выше код настолько неэффективен, насколько это возможно.

person gTcV    schedule 04.02.2014