Код в сортировке слиянием в C не работает должным образом - PullRequest
Новая
       65

Код в сортировке слиянием в C не работает должным образом

1 голос
/ 30 мая 2020 
int lb = 0, ub = 8, mid;   //ub=upper bound,lb=lower bound.
int i = 0, j = 0, k = 0;
int a[] = { 15, 5, 24, 8, 1, 3, 16, 10, 20 };
int b[10];

void mergeSort(int a[], int lb, int ub) {
    if (lb < ub) {
        mid = ((lb + ub) / 2);
        mergeSort(a, lb, mid);
        mergeSort(a, mid + 1, ub);
        merge(a, lb, mid, ub);
    }
}

void merge(int a[], int lb, int mid, int ub) {
    i = lb;
    j = mid + 1;
    k = lb;

    while (i <= mid && j <= ub) {
        if (a[i] <= a[j]) {
            b[k] = a[i];
            i++;
        } else {
            b[k] = a[j];
            j++;
        }
        k++;
    }

    if (i > mid) {
        while (j <= ub) {
            b[k] = a[j];
            j++;
            k++;
        }
    } else {
        while (i <= mid) {
            b[k] = a[i];
            i++;
            k++;
        }
    }

    for (k = lb; k <= ub; k++) {
        a[k] = b[k];
    }
}

void printList(int A[]) {
    for (k = 0; k <= 8; k++) {
        printf("%d\n", A[k]);
    }
    printf("done\n");
}

int main() {
    printList(a);
    mergeSort(a, 0, 8);
    printList(a);
}

Я думаю, что код mergesort и merge не является проблемой, проблема в том, что я проверял код много раз, но не могу найти ошибки, поэтому я надеюсь, что кто-то сможет объяснить мне, где это проблемы, спасибо всем, кто пытается помочь !!

вывод, когда я запускаю код: 

5
15
8
1
3
16
10
20
24
done

, который не является отсортированным списком.

1 Ответ

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

Проблема в том, что mid является глобальной переменной, поэтому она изменяется рекурсивным вызовом mergeSort(a, lb, mid);, и другое значение используется для второго рекурсивного вызова mergeSort(a, mid + 1, ub);, но другое значение используется для последнего вызова merge(a, lb, mid, ub); приводит к неожиданным результатам и потенциально может вызывать неопределенное поведение.

Не использовать глобальные переменные. Определите оба массива в main, сделайте i, j, k и mid локальные переменные в merge и mergeSort и передайте вспомогательный массив b в merge и mergeSort .

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

#include <stdio.h>

void merge(int a[], int lb, int mid, int ub, int b[]) {
    int i = lb;
    int j = mid + 1;
    int k = lb;

    while (i <= mid && j <= ub) {
        if (a[i] <= a[j]) {
            b[k] = a[i];
            i++;
        } else {
            b[k] = a[j];
            j++;
        }
        k++;
    }
    if (i > mid) {
        while (j <= ub) {
            b[k] = a[j];
            j++;
            k++;
        }
    } else {
        while (i <= mid) {
            b[k] = a[i];
            i++;
            k++;
        }
    }
    for (k = lb; k <= ub; k++) {
        a[k] = b[k];
    }
}

void mergeSort(int a[], int lb, int ub, int b[]) {
    if (lb < ub) {
        int mid = (lb + ub) / 2;
        mergeSort(a, lb, mid, b);
        mergeSort(a, mid + 1, ub, b);
        merge(a, lb, mid, ub, b);
    }
}

void printList(int A[], int len) {
    for (int k = 0; k < len; k++) {
        printf(" %d", A[k]);
    }
    printf("\n");
}

int main() {
    int a[] = { 15, 5, 24, 8, 1, 3, 16, 10, 20 };
    int len = sizeof(a) / sizeof(a[0]);
    // make b a temporary array the same size as a
    int b[len];

    printf("before:");
    printList(a, len);
    mergeSort(a, 0, len - 1, b);
    printf("after:");
    printList(a, len);
    return 0;
}

Вывод: 

before: 15 5 24 8 1 3 16 10 20
after: 1 3 5 8 10 15 16 20 24

Обратите внимание, что это менее подвержено ошибкам при передаче ub в качестве индекса для после последнего среза, длина среза составляет ub - lb, и вам не нужно никаких запутанных настроек +1 / -1. Кроме того, нет необходимости копировать оставшиеся элементы из правой половины, поскольку они уже находятся в правильной позиции в целевом массиве.

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

#include <stdio.h>

void merge(int a[], int lb, int mid, int ub, int b[]) {
    int i = lb;
    int j = mid;
    int k = lb;

    while (i < mid && j < ub) {
        if (a[i] <= a[j]) {
            b[k++] = a[i++];
        } else {
            b[k++] = a[j++];
        }
    }
    while (i < mid) {
        b[k++] = a[i++];
    }
    for (i = lb; i < k; i++) {
        a[i] = b[i];
    }
}

void mergeSort(int a[], int lb, int ub, int b[]) {
    if (ub - lb >= 2) {
        int mid = lb + (ub - lb) / 2;
        mergeSort(a, lb, mid, b);
        mergeSort(a, mid, ub, b);
        merge(a, lb, mid, ub, b);
    }
}

void printList(int A[], int len) {
    for (int k = 0; k < len; k++) {
        printf(" %d", A[k]);
    }
    printf("\n");
}

int main() {
    int a[] = { 15, 5, 24, 8, 1, 3, 16, 10, 20 };
    int len = sizeof(a) / sizeof(a[0]);
    // make b a temporary array the same size as a
    int b[len];

    printf("before:");
    printList(a, len);
    mergeSort(a, 0, len, b);
    printf("after:");
    printList(a, len);
    return 0;
}
...