Алгоритм сортировки слиянием работает некорректно

Вопрос:

В рамках домашнего задания мне нужно иметь возможность реализовать сортировку слиянием, используя структуру в качестве основного аргумента. Поскольку до сегодняшнего дня я не был знаком с сортировкой слиянием, я попытался написать свою собственную ее реализацию. По какой-то причине я не могу заставить его работать.

Вот мой код:

 #include<iostream>
#include<stdlib.h>

using namespace std;

struct MergeArgument
{
    int *numArray;
    int *tempArray;
    int lowIndex, highIndex;
};

void merge(MergeArgument*);
void merge_sort(MergeArgument*);

int main(int argc, char** argv)
{   int SIZE = 25;
    MergeArgument arg;
    int arr[SIZE];
    int temp[SIZE];

    for(int k = 0; k < SIZE; k  )
    {
        arr[k] = rand() % 100;
        cout << arr[k] << " ";
    }

    arg.numArray = arr;
    arg.tempArray = temp;
    arg.lowIndex = 0;
    arg.highIndex = SIZE - 1;

    cout << endl;

    merge_sort(amp;arg);

    cout << "Sorted array: n";

    for (int i = 0; i < SIZE; i  )
        cout << arr[i] << " ";
    cout << endl;

    return 0;
}

void merge_sort(MergeArgument *arg)
{   int tempHigh, tempLow;
    if(arg->lowIndex < arg->highIndex)
    {
        tempHigh = arg->highIndex;
        tempLow = arg->lowIndex;
        arg->highIndex = (tempHigh   tempLow) / 2;
        merge_sort(arg);
        arg->highIndex = tempHigh;
        arg->lowIndex = ((tempHigh   tempLow) / 2)   1;
        merge_sort(arg);
        arg->lowIndex = tempLow;
        merge(arg);
    }

}

void merge(MergeArgument *arg)
{   int low = arg->lowIndex, mid = ((arg->lowIndex   arg->highIndex) / 2), high = arg->highIndex;
    int i = low, lowCounter = low, highCounter = mid   1;

    while((lowCounter <= mid) amp;amp; (highCounter <= high))
    {
        if(arg->numArray[lowCounter] < arg->numArray[highCounter])
        {
            arg->tempArray[i] = arg->numArray[lowCounter];
            lowCounter  ;
        }
        else
        {
            arg->tempArray[i] = arg->numArray[highCounter];
            highCounter  ;
        }
        i  ;
    }

    if (lowCounter < mid)
    {
        for (int k = lowCounter; k < mid; k  )
        {
            arg->tempArray[i] = arg->numArray[k];
            i  ;
        }
    }
    else
    {
        for (int k = highCounter; k <= arg->highIndex; k  )
        {
            arg->tempArray[i] = arg->numArray[k];
            i  ;
        }

    }

    for(int k = arg->lowIndex; k <= arg->highIndex; k  )
    {
        arg->numArray[k] = arg->tempArray[k];
    }
}

Вот результат, который я получаю:

 83 86 77 15 93 35 86 92 49 21 62 27 90 59 63 26 40 26 72 36 11 68 67 29 82    
Sorted array:  
11 -1216235240 15 0 21 26 -1079135248 26 27 -1079135396 29 -1216770650 35 -1216235240 49 -1216492084 59 0 68 72 82 83 0 86 82

Кто-нибудь может указать, что именно я делаю не так?

1. Нет необходимости копировать теги в заголовок.

2. Для программы на C это очень похоже на C для меня.

3. Это очень грубый код, я просто хочу, чтобы сортировка слиянием работала, прежде чем я перейду к большой части задания. К тому времени, когда я закончу с этим, он будет выглядеть как C .

4. Я пытаюсь выяснить, как вы могли бы заставить его работать только с одним экземпляром MergeArgument , и только один аргумент передается merge() .

5. @michaelnett — я не уверен, что вижу достаточно локальных переменных.

Ответ №1:

Это довольно близко к работе, хотя вы можете рассмотреть некоторые комментарии, сделанные людьми, чтобы сделать это более похожим на C . Без сомнения, это из с трудом приобретенного опыта, что никогда не хватает времени, чтобы вернуться и сделать то, что вы действительно должны делать.

Проблема, которую я вижу, здесь, в merge :

 if (lowCounter < mid)
{
    for (int k = lowCounter; k < mid; k  )
    {
        arg->tempArray[i] = arg->numArray[k];
        i  ;
    }
}

Возможно, вам захочется сравнить и сопоставить границы здесь с начальным циклом.