合并排序不起作用？

Question

我在让我的合并排序功能与我的教授给我的规范一起工作时遇到了一些问题。一直盯着 VS 和 Google 想弄明白这个家伙。

提供的算法：

arrayFunctions.h

template<class T>
void printArray(T arr[], int numElements)
{
    cout << "(";

    for (int i = 0; i < numElements; i++)
    {

        cout << arr[i];

        if (i < numElements - 1)
            cout << ", ";
    }

    cout << ")" << "\n\n";
}

template <class T>
void setArray(T to[], T from[], int size)
{
    for (int i = 0; i < size; i++)
        to[i] = from[i];
}

template <class T>
void setArray(T to[], T from[], int size1, int size2)
{
    int size = size1;
    if (size2 < size1) size = size2;

    setArray(to, from, size);
}

主要

const int NUM = 5;

int originalArray[NUM] = { 4, 2, 5, 3, 1 };
int newArray[NUM];

cout << "Original:\n";
printArray(originalArray, NUM); //prints an array with formatting

// Merge Sort
setArray(newArray, originalArray, NUM); //set's newArray to the same values of originalArray
mergeSort(newArray, 0, NUM - 1);

cout << "Merge Sort:\n";
printArray(newArray, NUM);

pause();

运行main时的输出为：

原文： (4, 2, 5, 3, 1 )

合并排序： (0, 0, 0, -33686019, 1)

合并：

template <class T>
void merge(T L[], int lowerBound, int mid, int upperBound)
{
    // Get size for new arrays
    int size1 = mid - lowerBound;
    int size2 = upperBound - mid;

    // Create Temporary Arrays
    T * tmp1 = new T[size1 + 1]();
    T * tmp2 = new T[size2 + 1]();


    // Populate both arrays from original
    for (int i = 0; i < size1; i++)
        tmp1[i] = L[lowerBound + i];

    for (int j = 0; j < size2; j++)
        tmp2[j] = L[mid + j];

    tmp1[size1] = numeric_limits<T>::max();
    tmp2[size2] = numeric_limits<T>::max();

    int i = 0;
    int j = i;

    for (int k = lowerBound; k < upperBound; k++)
    {
        if (tmp1[i] <= tmp2[j])
        {
            L[k] = tmp1[i];
            i++;
        }
        else
        {
            L[k] = tmp2[j];
            j++;
        }
    }

    delete[] tmp1;
    delete[] tmp2;
}

合并排序：

template<class T>
void mergeSort(T L[], int lowerBound, int upperBound)
{
    if (lowerBound < upperBound)
    {
        int mid = (lowerBound + upperBound) / 2;

        mergeSort(L, lowerBound, mid);
        mergeSort(L, mid + 1, upperBound);

        merge(L, lowerBound, mid, upperBound);
    }
}

所以...我做错了什么？将不胜感激朝着正确方向前进。

Answer 1

// tmp1[size1 + 1] = (infinity?)
// tmp2[size2 + 1] = (infinity?)

这是破坏合并的代码部分，想一想如果你有两个列表，其中多了 1 个元素，那么它们应该会发生什么，请参阅：

// Create Temporary Arrays
T * tmp1 = new T[size1 + 1]();
T * tmp2 = new T[size2 + 1]();

这意味着它们对于 2 个值可能看起来像这样

foo = [1,2,?]
bar = [3,4,?]

问号将是一些数字，但您无法知道是什么，如果您然后运行在循环内进行几次比较，您将可以说 i = 2 , j == 0 为简单起见，现在你尝试做比较：

if (foo[2] <= bar[0])

这与

相同

if (? <= 3)

意味着你有一个未定义的行为，更糟糕的是你可能会去 i = 3 并开始查看随机内存。所以总而言之，（无穷大？） 以某种聪明的方式。

Answer 2

这是一个简单的错误。

T * tmp1 = new T[size1 + 1]();
...
tmp1[size1 + 1] = numeric_limits<T>::max();
           ^^^

数组索引从 0 到 n-1，而不是 n。

Answer 3

问题 1：哨兵

infinity 被注释掉是问题之一。

// tmp1[size1] = (infinity?)
// tmp2[size2] = (infinity?)

它被用作哨兵，所以当你到达tmp1（或tmp2）的最后位置时，它会确保你从另一个数组中复制所有其他元素， tmp2（或tmp1）。您可以在此处使用 std::numeric_limits<T>::max().

表示 inf

@Petter 很好地描述了为什么会出现这个问题。

问题 2：初始化

你的另一个问题似乎是在合并数组之前的初始化中：

int i = 1;
int j = i;

伪代码从 1 开始索引，而它应该从 0.

开始

问题 3：索引

正如@MarkRansom 所指出的，索引范围应该从0 到size1，而不是size1 + 1。

tmp1[size1 + 1] = numeric_limits<T>::max();

Answer 4

在C++合并函数中，L[]的右半部分以mid+1开始，所以第二个populate循环应该是：

    for (int j = 0; j < size2; j++)
        tmp2[j] = L[mid + j + 1];

在提供的算法中，索引从 1 到 n，因此第一个填充循环是 TMP1[i] ← L[lowerBound + i - 1]。对于 C++，索引从 0 到 n-1，因此 C++ 首先填充循环：tmp1[i] = L[lowerBound + i];是正确的，但是第二个循环需要改成tmp2[j] = L[mid + j + 1]; .

Answer 5

抱歉近两周忘记回复:/

这是一个错误，但我找到了它们并让它工作了。感谢所有帮助过的人。

已更改

int size1 = mid - lowerBound;
int size2 = upperBound - mid;

到

int size1 = mid - lowerBound + 1;
int size2 = upperBound - mid;

已更改

for (int j = 0; j < size2; j++)
    tmp2[j] = L[mid + j];

到

for (int j = 0; j < size2; j++)
    tmp2[j] = L[mid + j + 1];

已更改

for (int k = lowerBound; k < upperBound; k++)
{
    if (tmp1[i] <= tmp2[j])
    {
        L[k] = tmp1[i];
        i++;
    }
    else
    {
        L[k] = tmp2[j];
        j++;
    }
}

到

for (int k = lowerBound; k <= upperBound; k++)
{
    if (tmp1[i] <= tmp2[j])
    {
        L[k] = tmp1[i];
        i++;
    }
    else
    {
        L[k] = tmp2[j];
        j++;
    }
}

合并排序不起作用？

Merge Sort Not Working?

c++

algorithm

sorting

mergesort

问题 1：哨兵

问题 2：初始化

问题 3：索引