Ошибки в Void Merge - PullRequest
Новая
       10

Ошибки в Void Merge

0 голосов
/ 15 сентября 2018

У меня возникли проблемы при попытке выяснить, как исправить этот код, который я написал для Mergesort.

Намеченный результат состоял в том, чтобы вывести отсортированный массив входных данных, но функция void merge содержит ошибки, которые приводят клибо в несортированном массиве, либо в массиве действительно больших или маленьких чисел.

Я много раз пытался их исправить, но результат все равно не получается идеально.

Можете ли выпосмотрите и скажите, что я делаю не так? 

#include "pch.h"
#include <iostream>

using namespace std;

void merge(int* arr, int p, int q, int r) {
    //copy A[p.q] into L
    //and A[q+1.r] into R

    int i, j, k;
    int n1 = q - p + 1;
    int n2 = r - q;

    int* L = new int[n1+1];
    int* R = new int[n2+1];

    for (i = 1; i <= n1; i++) {
        L[i] = arr[p+i-1];
    }

    for (j = 1; j <= n2; j++){
        R[j] = arr[q+j];
    }

    L[n1+1] = 99999;
    R[n2+1] = 99999; //represents infinity
    i = j = 1;

    for (k = p; k <= r; k++)
    {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i = i + 1;
        }
        else {
            arr[k] = R[j];
            j = j + 1;
        }
        return;
    }
}


void mergesort(int* arr, int p, int r) {


    if (p < r) {
        int q = floor((p + r) / 2);
        mergesort(arr, p, q);
        mergesort(arr, q + 1, r);
        merge(arr, p, q, r);

    }
    return;
}


int main() {

    int r;
    cin >> r;

    int* arr = new int[r];

    for (int i = 0; i < r; i++) {
        int num;
        cin >> num;
        arr[i] = num;
    }

    int p = 0;
    //sortint function
    mergesort(arr,p,r);

    for (int i = 0; i < r; i++) {
        cout << arr[i] << ";";
    }
    return 0;
}
...