Код алгоритма сортировки слиянием приводит к повреждению кучи - PullRequest
Новая
       41

Код алгоритма сортировки слиянием приводит к повреждению кучи

0 голосов
/ 29 сентября 2019

Я пытаюсь написать программу на С ++, которая сортирует 2 несортированных массива с помощью сортировки слиянием.Однако мой код неправильно сортирует массивы и выводит элементы массива точно в том же порядке, в котором они были введены.Например, я вставил следующий ввод и получил следующий вывод:

4 1 2 3 1 5

4 1 2 3 1 5

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

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

void Merge(int*arr, int left, int mid, int right) {
    int half1 = mid - left + 1;
    int half2 = right - mid;
    int* lowerhalf = new int[half1];
    int* upperhalf = new int[half2];

    for (int i = 0; i < half1; i++) {
        lowerhalf[i] = arr[left + i];
    }

    for (int j = 0; j < half2; j++) {
        upperhalf[j] = arr[mid + 1 + j];
    }

    int i = 0;
    int j = 0;
    int k = half1;
    while (i < half1 && j < half2) {
        if (lowerhalf[i] <= upperhalf[j]) {
            arr[k] = lowerhalf[i];
            i = i + 1;
        }
        else {
            arr[k] = upperhalf[j];
            j = j + 1;
        }
        k++;
    }
    while (i < half1) {
        arr[k] = lowerhalf[i];
        i = i + 1;
        k = k + 1;
    }
    while (j < half2) {
        arr[k] = upperhalf[j];
        j = j + 1;
        k = k + 1;
    }

}
void MergeSort(int* arr, int left, int right) {
    if (left < right) {
        int midpoint = left + (right-1)/2;
        MergeSort(arr, left, midpoint);
        MergeSort(arr, midpoint + 1, right);
        Merge(arr, left, midpoint, right);
    }
}



int main() {
    int A;
    int B;
    cin >> A >> B;

    int* items1 = new int[A];
    int* items2 = new int[B];

    for (int i = 0; i < A; i++) {
        cin >> items1[i];
    }

    for (int i = 0; i < B; i++) {
        cin >> items2[i];
    }
    MergeSort(items1, 0, A-1);
    MergeSort(items2, 0, B - 1);


    for (int i = 0; i < A; i++) {
        cout << items1[i] << " ";
    }
    cout << "\n";

    for (int i = 0; i < B; i++) {
        cout << items2[i] << " ";
    }

    delete items1;
    delete items2;

    return 0;
}
...