合并排序与字符串向量 C++

Question

大家好，我是递归的菜鸟，我想用头撞墙。我看了一些视频，阅读了本章，并且已经尝试找出这个问题的答案已经超过 6 个小时了，但没有成功。我的教授给了我们以下代码，我们必须从那里 mod 它。注意：我们正在从文件中读取 52k 个单词，然后使用此算法对它们进行排序。不确定这是否重要，但我想我会添加信息以防万一。
包括

using namespace std;

vector<int> MergeUsingArrayIndices(const vector<int> & LHS,
                               const vector<int> & RHS)
{
vector<int> ToReturn;

int i = 0;  // LHS index
int j = 0;  // RHS index

while ((i < LHS.size()) && (j < RHS.size()))
{
    if (LHS[i] < RHS[j])
    {
        ToReturn.push_back(LHS[i]);
        ++i;
    }
    else
    {
        ToReturn.push_back(RHS[j]);
        ++j;
    }
}

while (i < LHS.size())
{
    ToReturn.push_back(LHS[i]);
    ++i;
}

while (j < RHS.size())
{
    ToReturn.push_back(RHS[j]);
    ++j;
}

return ToReturn;
}

除了现在我们必须从一个向量中完成这项工作。这是我到目前为止所拥有的。

vector<string> MergeUsingArrayIndices(vector<string> & LHS,
int START, int MID, int MIDPLUSONE, int END)
{

    vector<string> ToReturn;
    int i = 0;  // LHS index
    int j = MIDPLUSONE;  // RHS index

    while ((i <= MID) && (j <= END))
    {
        if (LHS[i] < LHS[j])
        {
            ToReturn.push_back(LHS[i]);
            ++i;
        }
        else
        {
            ToReturn.push_back(LHS[j]);
            ++j;
        }
    }

    while (i <= MID)
    {
        ToReturn.push_back(LHS[i]);
        ++i;
    }

    while (j <= END)
    {
        ToReturn.push_back(LHS[j]);
        ++j;
    }
    for (int k = 0; k < ToReturn.size(); ++k)
    {
        LHS[k] = ToReturn[k];
    }
    return ToReturn;

}

此外，这是函数之前的调用。

void MergeSort(vector<string> & VECTOR, int START, int END)
{

if (END > START)
{
    int MID = (START + END) / 2;
    MergeSort(VECTOR, START, MID);
    MergeSort(VECTOR, MID + 1, END);
    MergeUsingArrayIndices(VECTOR, START, MID, (MID+1), END);
}
}

void Merge(std::vector<string> & VECTOR)
{

MergeSort(VECTOR, 0, VECTOR.size()-1);
}

Console Screen Shot

基本上是在排序，但不是很好，因为并非所有内容都按字母顺序排列。那只是列表中的一小部分单词。

谢谢你和最诚挚的问候，

不要结婚。

更新：PNKFELIX 它尝试了以下；

        vector<string> ToReturn;
        int i = START;       // LHS index
        int j = MIDPLUSONE;  // RHS index

    while (i <= MID && j <= END)
    {
        if (LHS[i] <= LHS[j])
        {
            ToReturn[START] = LHS[i];
            //ToReturn.push_back(LHS[i]);
            ++START;
            ++i;
        }

等等，但这使代码变得更糟，所以我确定这不是您所指的。我已经起床好几天想弄明白了，我睡不着……

你指出的一件事让我很困扰，因为我明白为什么它没有发生但无法修复的是电话

我猜这就是您使用苹果、梨、橙子和香蕉示例的原因。（顺便说一下，非常聪明）。你可以把马牵到水边，但不能让它喝水。但是，我仍然看不到如何解决这个问题？我试着更换我的 i = 0;我现在看到 i = START 这可能是比较右侧的罪魁祸首，因为它应该从那个位置开始，但它实际上让我的代码变得更糟？我还缺少什么？

我有太多事情要做，当教授做这样的事情时我无法忍受（我的社区大学不适合 CIS，我的教授以前从未教过这个 class）。在我弄清楚之前我不能休息，但是教科书太过我的头脑（教授甚至在学期开始时为教科书道歉，说它对我们来说太先进了，但这是他们给了他的）并且完全使用了不同的方法（两个单独的数组而不是一个向量）。我应该用 START 做什么？我在这上面花了很多时间，很想知道答案。也许这让我变得懒惰，但有一点你只能考虑这么多。我喜欢学习，但这不是学习，因为我已经达到了极限。我遗漏了一些东西，不知道如何开始检查它是什么。我假设每个向量比较的右侧未排序，但我该如何解决？是因为开始并不总是零（例如：右侧）吗？我不擅长排序算法（因为我不是很聪明（虽然我研究分配）），但这是一个新的转折。这就像递给某人一个损坏的冒泡排序并要求他们在桌面上检查它，修复它的问题，并使其更有效率，但他们以前从未见过一个工作。

Answer 1

在 if 条件下使用 strcmp(LHS[i],LHS[j])<0

Answer 2

像这样的问题的好处是这里没有特定于 C++ 的内容。人们可以采用建议的代码并将其移植到几乎任何其他合理的语言（例如 JavaScript），然后在那里调试它以确定出了什么问题。

在任何程序中，一个好的做法是记录代码的假设和不变量。如果这些不变量足够简单，您甚至可以通过 assert 语句检查它们是否包含在代码本身中。

所以，让我们看看：从 MergeSort 如何调用 MergeUsingArrayIndices 来看，你的方法似乎是一种递归分而治之的方法：你首先将输入分成两部分一个中点元素，对分割输入的每一边进行排序，然后合并两部分。

从那个高级描述中，我们可以确定一对必须保持进入 MergeUsingArrayIndices 的不变量：LHS 的左半部分必须排序，LHS 的右半部分也必须排序.我们可以在合并向量时检查这两个条件是否成立，这可能有助于我们找出出错的地方。

我将原始代码尽可能忠实地移植到 Rust（我的首选编程语言），然后添加了一些断言和一些打印语句，以便我们可以看到断言在哪里失败。

（还有一个我在上面忘记提到的变化：我还从 MergeUsingArrayIndices 中删除了未使用的 return 值。您正在构建的数组仅用作临时存储稍后将复制到 LHS；您永远不会使用 return 值，因此我们可以将其从函数的类型中完全删除。）

这是运行围栏中的代码：

https://play.rust-lang.org/?gist=bd61b9572ea45b7139bf081cb51dc491&version=stable&backtrace=0

一些引导性问题：

断言报告LHS[i]实际上不小于LHS[i+1]时比较的是什么指标？
打印输出报告矢量何时应按特定子范围排序：0...0、1...1、0...1 等等。您在上面找到的索引（假设它们与我找到的相同）不在这些子范围之一内；所以我们实际上没有理由试图声称 LHS[i] 小于 LHS[i+1]！那么发生了什么，为什么代码认为它们应该落入向量的排序子范围内？
第一个强烈提示：我留下了编译器关于代码的警告。
第二个强烈提示：尝试做我在 MergeUsingArrayIndices 函数上方评论中留下的练习。

合并排序与字符串向量 C++

Merge Sort With String Vectors C++

c++

string

mergesort

vector