Что-то не так с порядковым номером массива в сортировке слиянием? - PullRequest
Новая
       23

Что-то не так с порядковым номером массива в сортировке слиянием?

0 голосов
/ 29 февраля 2020

Поэтому я пытаюсь реализовать сортировку слиянием в C ++, и в этой версии используется O (n) пространственной сложности.
Этот алгоритм написан с использованием псевдокода, найденного в книге «Основы алгоритмов».
Я думаю, что есть некоторые ошибки при использовании индекса в функции merge2.
Переменные, оканчивающиеся на _tmp, используются для манипулирования массивом U, а переменные без _tmp используются для манипулирования массивом S. 

#include <iostream>

int n = 8;
int S[8] = { 0, };

void mergeSort2(int low, int high);
void merge2(int low, int mid, int high);

void mergeSort2(int low, int high) {
    int mid;
    if (low < high) {
        mid = (low + high) / 2;
        mergeSort2(low, mid);
        mergeSort2(mid + 1, high);
        merge2(low, mid, high);
    }
}

void merge2(int low, int mid, int high) {
    int i, j, k;
    int i_tmp, j_tmp, k_tmp;
    int high_tmp = high - low;
    int low_tmp = 0;
    int mid_tmp = high / 2;
    i_tmp = low_tmp; j_tmp = mid_tmp + 1; k_tmp = low_tmp;
    i = low; j = mid + 1; k = low;
    int* U = new int[high_tmp + 1];
    while (i <= mid && j <= high) {
        if (S[i] < S[j]) {
            U[k_tmp] = S[i];
            i++;
            i_tmp++;
        }
        else {
            U[k_tmp] = S[j];
            j++;
            j_tmp++;
        }
        k++;
        k_tmp++;
    }
    if (i_tmp > mid_tmp) {
        //move S[j] through S[high] to U[k] through U[high-1]
        for (int r = j, s = k_tmp; r < high, s < high_tmp; r++, s++) {
            U[s] = S[r];
        }
    }
        else {
        //move S[i] through S[mid] to U[k] through U[high-1]
        for (int r = i, s = k_tmp; r < mid, s < high_tmp; r++, s++) {
            U[s] = S[r];
        }
    }
    //move U[low] through U[high] to S[low] through S[high-1]
    for (int r = low_tmp, s = low; r < high_tmp, s < high; r++, s++) {
        S[s] = U[r];
    }
    delete U;
}

int main() {
    std::cout << "Enter the elements of the array S (size : " << n << ") : ";
    for (int i = 0; i < n; i++) {
        std::cin >> S[i];
    }
    mergeSort2(0, n);
    std::cout << std::endl;
    std::cout << "Result of array S sorted in an ascending order : ";
    for (int i = 0; i < n; i++) {
        std::cout << S[i] << "  ";
    }
    std::cout << std::endl << std::endl;
    return 0;
}

1 Ответ

1 голос
/ 29 февраля 2020

Как отмечается в комментариях, проблема заключается в тестовых условиях ваших for циклов с использованием оператора запятой. Как описано в cppreference :

В выражении E1, E2 запятой вычисляется выражение E1, его результат отбрасывается ... до начала вычисления выражения E2 .. .

Итак, в l oop: 

for (int r = j, s = k_tmp; r < high, s < high_tmp; r++, s++) {
   //...

выражение r < high равно никогда не использовалось и l oop будет только завершается, когда выражение s < high_tmp оценивается как false.

Если вы хотите, чтобы l oop заканчивался, когда или выражение ложно, вам нужно объединить два теста с && (логический оператор И): 

for (int r = j, s = k_tmp; r < high && s < high_tmp; r++, s++) {
   //...
...