在递归合并排序期间中止（核心转储）

Question

在按引用传递时实现递归归并排序时遇到问题。 basic_merge_sort 是 main.cpp 的入口点，我在这里按值传递，因为我对一堆排序使用相同的数组。我得到的错误是 malloc(): invalid size (unsorted) Aborted (core dumped)，使用 gcc 和 Makefile。使用 Counter class 中的静态成员来跟踪递归期间的比较。我也尝试不使用指针，而是使用静态 class 成员向量，但没有成功。有什么想法或建议吗？提前致谢。

#include "merge.hpp"
#include "selection.hpp"

using namespace std;

int Counter::count{0}; //lets start count from 0

int basic_merge_sort(vector<double> holder_array) //entry point
{
    int end = holder_array.size() - 1;
    mpartition(&holder_array, 0, end);
    return Counter::count;
}

void merge_sort(vector<double> *holder_array, int start, int end, int middle)
{
    int i = start, j = middle + 1, k = 0;
    vector<double> temp(end - start + 1, 0.0); 

    while (i <= middle && j <= end)
    {
        if (holder_array->at(i) < holder_array->at(j))
        {
            temp[k] = holder_array->at(i); 
            k++;
            i++;
            Counter::count++;
        }
        else
        {
            temp[k] = holder_array->at(j);
            k++;
            j++;
            Counter::count++;
        }
    }

    while (i <= middle)
    {
        temp[k] = holder_array->at(i);
        k++;
        i++;
        Counter::count++;
    }

    while (j <= end)
    {
        temp[k] = holder_array->at(j);
        k++;
        j++;
        Counter::count++;
    }
    for (i = start; i <= end; i++)
    {
        holder_array->at(i) = temp[i - start];
    }
}

void mpartition(vector<double> *holder_array, int start, int end)
{
    int middle;
    if (start < end)
    {
        middle = (start + end) / 2;
        mpartition(holder_array, start, middle);
        mpartition(holder_array, middle + 1, end);
        merge_sort(holder_array, start, end, middle);
    }
}

Answer 1

您的代码中存在多个问题：

您没有通过引用传递向量：basic_merge_sort 获取向量的副本，因此不会对传递给它的数组进行排序，而只是对副本进行排序。
mpartition接受一个指向向量的指针，这与通过引用传递不完全相同。
排除约定 end 令人困惑且容易出错，您应该在 C++ 中使用更惯用的约定并考虑排除上限。

这是修改后的版本：

#include "merge.hpp"
#include "selection.hpp"

using namespace std;

int Counter::count{0}; //lets start count from 0

int basic_merge_sort(vector<double>& array)
{
    mpartition(array, 0, array.size());
    return Counter::count;
}

void merge_sort(vector<double>& array, size_t start, size_t middle, size_t end)
{
    size_t i = start, j = middle, k = 0;
    vector<double> temp(end - start, 0.0); 

    while (i < middle && j < end) {
        if (array[i] < array[j]) {
            temp[k++] = array[i++]; 
            Counter::count++;
        } else {
            temp[k++] = array[j++];
            Counter::count++;
        }
    }

    while (i < middle) {
        temp[k++] = array[i++];
        Counter::count++;
    }

    while (j < end) {
        temp[k++] = array[j++];
        Counter::count++;
    }
    for (i = start; i < end; i++) {
        array[i] = temp[i - start];
    }
}

void mpartition(vector<double>& array, size_t start, size_t end)
{
    if (end - start >= 2) {
        size_t middle = start + (end - start) / 2;
        mpartition(holder_array, start, middle);
        mpartition(holder_array, middle, end);
        merge_sort(holder_array, start, middle, end);
    }
}

在递归合并排序期间中止（核心转储）

Aborted (core dumped) during recursive merge sort

c++

malloc

mergesort

coredump

pointers