Пожалуйста, обратите внимание на ошибку в этом коде сортировки слиянием - PullRequest
Новая
       59

Пожалуйста, обратите внимание на ошибку в этом коде сортировки слиянием

0 голосов
/ 08 мая 2020

Я предоставил код для сортировки массива с использованием алгоритма сортировки слиянием, я не могу найти ошибку, этот код не дает правильно отсортированный массив на выходе. Функция mergesort вызывается рекурсивно для разделения массива, пока его размер не уменьшится до 1. Затем несколько массивов объединяются с помощью функции merge. 

#include <bits/stdc++.h>

using namespace std;

void merge(int a[], int m, int l, int h) {
    int n1 = m - l + 1, n2 = h - m;
    int t1[n1], t2[n2];
    for (int i = 0; i < n1; i++) {
        t1[i] = a[i + l];
    }
    for (int i = 0; i < n2; i++) {
        t2[i] = a[i + m + 1];
    }
    int k = 0, p = 0, r = 0;
    while (k < n1 && p < n2) {
        if (t1[k] <= t2[p]) {
            a[r] = t1[k];
            k++;
            r++;
        } else {
            a[r] = t2[p];
            p++;
            r++;
        }
    }
    while (k < n1) {
        a[r] = t1[k];
        k++;
        r++;
    }
    while (p < n2) {
        a[r] = t2[p];
        p++;
        r++;
    }
}

void mergesort(int a[], int l, int h) {
    if (l < h) {
        int m = l + (h - l) / 2;
        mergesort(a, l, m);
        mergesort(a, m + 1, h);
        merge(a, m, l, h);
    }
}

int main() {
    int a[5] = { 1, 2, 3, 4, 5 };
    mergesort(a, 0, 4);
    for (int i = 0; i < 5; i++) {
        cout << a[i] << " ";
    }
    return 0;
}

1 Ответ

1 голос
/ 08 мая 2020

Ошибка в функции merge: r следует инициализировать как l, а не 0. Вы не объединяете фрагменты в исходное положение.

Также обратите внимание, что последний l oop while (p < n2) в этой функции является избыточным: остальные элементы в правом фрагменте уже находятся в нужном месте в исходный массив.

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

void merge(int a[], int m, int l, int h) {
    int n1 = m - l + 1, n2 = h - m;
    int t1[n1], t2[n2];
    for (int i = 0; i < n1; i++) {
        t1[i] = a[i + l];
    }
    for (int i = 0; i < n2; i++) {
        t2[i] = a[i + m + 1];
    }
    int k = 0, p = 0, r = l;
    while (k < n1 && p < n2) {
        if (t1[k] <= t2[p]) {
            a[r] = t1[k];
            k++;
            r++;
        } else {
            a[r] = t2[p];
            p++;
            r++;
        }
    }
    while (k < n1) {
        a[r] = t1[k];
        k++;
        r++;
    }
}

Для дальнейшего упрощения кода сделаем еще несколько замечаний:

  • это менее запутанно используйте соглашение, согласно которому h должен быть первым индексом после конца среза. Таким образом, начальный вызов использует длину массива, и mergesort может вычислить длину среза как h - l.
  • имя переменной l выглядит сбивающе близко к номеру 1.
  • аргументы для merge обычно находятся в следующем порядке: l, m, h, а m - это индекс начала правого фрагмента.
  • правый фрагмент не требует сохранения .
  • использование массивов переменной длины с автоматикой c хранилище t1[n2] может вызвать переполнение стека для больших массивов.

Вот измененная версия: 

#include <bits/stdc++.h>

using namespace std;

void merge(int a[], int lo, int m, int hi) {
    int i, j, k;
    int n1 = m - lo;
    int t1[n1];
    for (i = 0; i < n1; i++) {
        t1[i] = a[lo + i];
    }
    i = 0;
    j = m;
    k = lo;
    while (i < n1 && j < hi) {
        if (t1[i] <= a[j]) {
            a[k++] = t1[i++];
        } else {
            a[k++] = a[j++];
        }
    }
    while (i < n1) {
        a[k++] = t1[i++];
    }
}

void mergesort(int a[], int lo, int hi) {
    if (hi - lo >= 2) {
        int m = lo + (hi - lo) / 2;
        mergesort(a, lo, m);
        mergesort(a, m, hi);
        merge(a, lo, m, hi);
    }
}

int main() {
    int a[5] = { 1, 5, 2, 4, 3 };
    mergesort(a, 0, 5);
    for (int i = 0; i < 5; i++) {
        cout << a[i] << " ";
    }
    cout << "\n";
    return 0;
}
...