сортировка слиянием в бесконечном цикле - PullRequest
Новая
       3

сортировка слиянием в бесконечном цикле

2 голосов
/ 04 апреля 2020

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

void merge_sort_recursive(int *arr, int left, int right) {
    int mid;
    while (left < right) { 
        mid = (left + right) / 2;
        merge_sort_recursive(arr, left, mid);
        merge_sort_recursive(arr, mid + 1, right);
        merge_recursive(arr, left, mid, right);
    }
    for (int i = 0; i < 4; i++)
        cout << arr[i] << " ";
    cout << endl;
}

void merge_recursive(int *arr, int left, int mid, int right) {
    int *buffer = new int[right + 1]; 
    int lPtr = left; 
    int rPtr = mid + 1;
    int bPtr = left; 

    while (lPtr <= mid && rPtr <= right) {
        if (arr[lPtr] < arr[rPtr]) 
            buffer[bPtr++] = arr[lPtr++];
        else
            buffer[bPtr++] = arr[rPtr++];
    }

    if (lPtr > mid) 
        for (int i = rPtr; i <= right; i++)
            buffer[bPtr++] = arr[i];
    else 
        for (int i = lPtr; i <= mid; i++)
            buffer[bPtr++] = arr[i];

    for (int i = left; i <= right; i++) 
        arr[i] = buffer[i]; 
}

1 Ответ

0 голосов
/ 04 апреля 2020

В вашем коде несколько проблем:

  • в функции merge_sort_recursive, вы не должны l oop while (left < right), а просто действовать рекурсивно if (left < right).
  • вы должны удалить вывод в merge_sort_recursive. Я полагаю, что он у вас есть только для целей отладки.
  • в функции merge_recursive вы выделяете временный массив размером right + 1. Это слишком много, достаточно right - left + 1 (с корректировкой значений индекса).
  • вы не delete временный массив, вызывая существенные утечки памяти,
  • тест в первое слияние l oop должно использовать <= вместо <,

Основная проблема - while l oop, которая предотвращает возврат из рекурсивных вызовов.

Вот модифицированная версия: 

void merge_sort_recursive(int *arr, int left, int right) {
    if (left < right) { 
        int mid = (left + right) / 2;
        merge_sort_recursive(arr, left, mid);
        merge_sort_recursive(arr, mid + 1, right);
        merge_recursive(arr, left, mid, right);
    }
}

void merge_recursive(int *arr, int left, int mid, int right) {
    int *buffer = new int[right - left + 1];
    int lPtr = left;
    int rPtr = mid + 1;
    int bPtr = 0;

    while (lPtr <= mid && rPtr <= right) {
        if (arr[lPtr] <= arr[rPtr]) 
            buffer[bPtr++] = arr[lPtr++];
        else
            buffer[bPtr++] = arr[rPtr++];
    }
    /* copy the remaining elements from the left part */
    while (lPtr <= mid) {
        buffer[bPtr++] = arr[lPtr++];
    }
    /* no need to copy the remaining elements from the right part 
       because they already are at the final position */
    for (int i = 0; i < bPtr; i++) {
        arr[left + i] = buffer[i];
    }
    delete[] buffer;
}
...