Saya mencoba menulis versi gabungan yang sepenuhnya rekursif Saya mendapatkan kesalahan segmentasi pada fungsi merge ketika saya mencoba memesan lebih dari 100k catatan, saya membaca online bahwa itu akan menjadi masalah stack overflow, terkait dengan VLA, tetapi saya tidak dapat mengetahuinya.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct _MBArray MBArray;

struct _MBArray {
    void ** array;
    int length;
};

void mergeSort(MBArray *mbarray, int start, int end, int (*compare)(void *, void *)) {
    if (start == end) {
        return;
    } else {
        int middle = (end + start) / 2;
        mergeSort(mbarray, start, middle, compare);
        mergeSort(mbarray, middle + 1, end, compare);
        merge(mbarray, start, middle + 1, end, compare, (mbarray->array)[middle + 1]);
        return;
    }
}

void merge(MBArray *mbarray, int startA, int startB, int length, int (*compare)(void *, void *),void *elem) {
    if (startA > startB - 1) {
        return;
    } else
    if (startB > length) {
        return;
    } else
    if ((*(compare))((mbarray->array)[startA], (mbarray->array)[startB])) {
        merge(mbarray, startA + 1, startB, length, compare, (mbarray->array)[startB]);
        return;
    } else {
        memcpy(mbarray->array + (startA + 1), mbarray->array + startA, (startB - startA) * sizeof(void *));
        (mbarray->array)[startA] = elem;
        merge(mbarray, startA + 1, startB + 1, length, compare, (mbarray->array)[startB + 1]);
        return;
    }
}
1
Alee 11 Mei 2021, 12:33

2 jawaban

Jawaban Terbaik

Fungsi merge dan mergesort Anda salah:

  • fungsi mergesort diberikan nilai indeks ke dalam larik sedemikian rupa sehingga start disertakan dan end dikecualikan. Berikut cara memperbaikinya:
void mergeSort(MBArray *mbarray, int start, int end,
               int (*compare)(void *, void *))
{
    if (end - start > 1) {
        int middle = start + (end - start) / 2;
        mergeSort(mbarray, start, middle, compare);
        mergeSort(mbarray, middle, end, compare);
        merge(mbarray, start, middle, end, compare);
    }
}

Fungsi merge harus disederhanakan. Jika Anda benar-benar bermaksud agar fungsi ini berulang alih-alih menggunakan array sementara, Anda mungkin berulang sebanyak length/2 kali sehingga kemungkinan akan menyebabkan tumpukan meluap lebih cepat daripada dengan mengalokasikan VLA dalam fungsi gabungan.

Berikut adalah fungsi merge berbasis VLA:

void merge(MBArray *mbarray, int low, int middle, int end,
           int (*compare)(void *, void *))
{
    int templen = middle - low;
    void *temp[templen];
    memcpy(temp, mbarray->array + low, sizeof(temp));
    int i = 0, j = middle, k = low;
    while (i < templen) {
        if (j >= end || compare(temp[i], mbarray->array[j])) {
            mbarray->array[k++] = temp[i++];
        else
            mbarray->array[k++] = mbarray->array[j++];
    }
}

Versi rekursif penuh harus menyimpan elemen dan berulang sebelum menyetelnya ke posisi akhirnya. Ini jauh lebih mahal dalam ruang tumpukan daripada mengalokasikan VLA sehingga stack overflow lebih mungkin terjadi. Mengalokasikan array sementara sekali dengan malloc() dan meneruskannya ke mergesort jauh lebih aman dan juga lebih efisien.

Berikut adalah fungsi rekursif penuh merge yang dimodifikasi:

void mergeRecur(MBArray *mbarray, int dest, int a0, int a1, int b0, int b1,
                int (*compare)(void *, void *))
{
    if (a0 < a1) {
        if (b0 >= b1 || compare(mbarray->array[a0], mbarray->array[b0])) {
            void *temp = mbarray->array[a0];
            mergeRecur(mbarray, dest + 1, a0 + 1, a1, b0, b1, compare);
            mbarray->array[dest] = temp;
        } else {
            void *temp = mbarray->array[b0];
            mergeRecur(mbarray, dest + 1, a0, a1, b0 + 1, b1, compare);
            mbarray->array[dest] = temp;
        }
    }
}

void merge(MBArray *mbarray, int low, int middle, int end,
           int (*compare)(void *, void *))
{
    mergeRecur(mbarray, low, low, middle, middle, end, compare);
}

Untuk array besar, saya akan merekomendasikan mengalokasikan array sementara sekali dan memanggil versi rekursif mergesort yang menggunakan array sementara alih-alih mengalokasikan VLA:

#include <stdlib.h>
#include <string.h>

struct _MBArray {
    void ** array;
    int length;
};

void mergeTemp(MBArray *mbarray, int low, int middle, int end,
               int (*compare)(void *, void *), void **temp)
{
    int templen = middle - low;
    int i = 0, j = middle, k = low;

    memcpy(temp, mbarray->array + low, sizeof(*temp) * templen);
    while (i < templen) {
        if (j >= end || compare(temp[i], mbarray->array[j])) {
            mbarray->array[k++] = temp[i++];
        else
            mbarray->array[k++] = mbarray->array[j++];
    }
}

void mergeSortTemp(MBArray *mbarray, int start, int end,
                   int (*compare)(void *, void *), void **temp)
{
    if (end - start > 1) {
        int middle = start + (end - start) / 2;
        mergeSortTemp(mbarray, start, middle, compare, temp);
        mergeSortTemp(mbarray, middle, end, compare, temp);
        mergeTemp(mbarray, start, middle, end, compare, temp);
    }
}

void mergeSort(MBArray *mbarray, int (*compare)(void *, void *)) {
    if (mbarray->length > 1) {
        void **temp = malloc(sizeof(*temp) * (mbarray->length / 2));
        mergeSortTemp(mbarray, 0, mbarray->length, compare, temp);
        free(temp);
    }
}
0
chqrlie 12 Mei 2021, 17:53

Masalahnya kemungkinan besar karena merge() memanggil dirinya sendiri untuk setiap elemen yang digabungkan. Akan lebih baik untuk memiliki fungsi entri untuk mergeSort() yang melakukan alokasi satu kali array kedua (pointer), kemudian meneruskan array kedua sebagai parameter ke MergeSortR() rekursif, dan menggabungkan bolak-balik antara dua array.

0
rcgldr 11 Mei 2021, 22:08