时间戳

首页 > 解决方案 > 如何正确创建合并排序函数？

c++ - 如何正确创建合并排序函数？

问题描述

这是针对我的计算机科学 C++ 数据结构课程的。

对于我的任务，我必须为升序和降序数组创建合并排序代码。

我的教授让我编译他的测试代码和我的文件代码。终端将打印出我的编码逻辑中的任何错误。

这是我运行文件时在终端中打印的错误：

   **** 测试合并排序 ****

测试简单的二元素合并：
好的

测试 20 元素合并（10 和 10）：OK

测试 21 元素合并：OK

排序空序列：OK

对大小为 2 的随机向量进行排序：
{48, 77}
好的

对大小为 3 的随机向量进行排序：
{48, 77, 64}
好的

对大小为 4 的随机向量进行排序：
{48, 77, 64, 2}
好的

对大小为 5 的随机向量进行排序：
{48、77、64、2、11}

失败：结果未排序：
{11、2、48、64、77}

这是我的代码：

void merge(int *input, int size, int *output, bool output_asc) {
    if (output_asc == true) { //sort ascending
        int i = 0;
        int j = size - 1;
        int k = 0;
        while (i <= j) {
            if (input[i] <= input[j]) {
                output[k++] = input[i++];
            } else {
                output[k++] = input[j--];
            }
        }
    } else
    if (output_asc == false) { //sort descending
        int i = 0;
        int j = size - 1;
        int k = 0;
        while (i <= j) {
            if (input[i] <= input[j]) {
                output[k++] = input[j--];
            } else {
                output[k++] = input[i++];
            }
        }
    }
}
     
void mergesort(int *input, int size, int *output, bool output_asc) {
    int begin = 0;
    int end = size - 1;
    if (begin >= end) {
        return;
    }
    int mid = (begin + end) / 2;

    mergesort(input, mid - 1, output, output_asc);
    mergesort(input, end, output, output_asc);

    merge(input, size, output, output_asc); 
}

int *mergesort(int *input, int size) {
    int *output = new int[size];
    mergesort(input, size, output, true);
    return output;
}

这是我的教授测试代码：

/* test_mergesort()
Test mergesort on a variety of inputs.
*/
bool test_mergesort() {
    cout << "Sorting empty sequence:";
    vector<int> no_data;

    int *no_data_sorted = mergesort(no_data);
    // No data means nothing to check!
    delete[] no_data_sorted;
    cout << "OK\n";

    vector<int> sizes = { 2, 3, 4, 5, 7, 8, 15, 16, 19, 20, 50, 64, 100, 128 };

    for (int s : sizes) {

        // Test sorting a vector of random data
        vector<int> data = make_random_vector(s);

        cout << "Sorting random vector of size " << s << ":\n" << data << "\n";

        int *data_sorted = mergesort(data);
        if (!is_sorted(data_sorted, data.size())) {
            cout << "FAILED: result is not sorted:\n";

            cout << "{";
            for (int *i = data_sorted; i != data_sorted + data.size() - 1; ++i)
                cout << *i << ", ";
            cout << data_sorted[data.size() - 1] << "}\n";

            return false;
        } else
        if (!is_permutation(&data[0], data.size(), data_sorted)) {
            cout << "FAILED: result is not a permutation of the input sequence:\n";
            cout << "{";
            for (int *i = data_sorted; i != data_sorted + data.size() - 1; ++i)
                cout << *i << ", ";
            cout << data_sorted[data.size() - 1] << "}\n";

            return false;
        } else
            cout << "OK\n";
    }    
    return true;
}

任何帮助将不胜感激，谢谢。

标签： c++data-structuresmergesort

解决方案

您的合并排序看起来非常复杂。从一个正确的简单低效版本开始。

然后更换零件以提高效率。

std::vector<int> merge( std::vector<int> a, std::vector<int> b );

这写起来容易 20 倍。编写并测试它。

然后写

std::vector<int> merge_sort( std::vector<int> in );

用一个简单的低效除法，递归，然后合并。

测试并确认它有效。

现在将它连接到您的教授测试代码。效率低下；将指针和大小复制到向量，进行排序，然后将其复制回来。确认您的教授测试通过。

如果您真的想要反向功能，请添加它。为合并添加一个布尔值，表示将其结果向后返回，并假设正确的参数是向后的。

接下来，围绕合并编写低效的包装器，将指针转换为向量并返回。它需要两个指针和两个大小，并假设右侧是向后的，就像矢量版本一样。

在一些数据上进行测试。确信你的分配是正确的。

写合并排序采用标准向量并调用那些指针包装的合并版本。用教授代码测试它。

现在你有了一个可靠的基于指针的合并测试工具。

采用外部合并排序，并使其以指针为输入并调用基于指针的合并。与教授测试工具一起测试。

现在采用内部合并函数并将其替换为内部使用指针的函数。

基本思路是先做简单正确。然后可以用更有效的东西替换一块。测试你的包装没有破坏任何东西。Thsn 使那一件更快。并再次测试。

只有当问题对您来说微不足道时，编写单个大型复杂优化系统才有效。

推荐阅读