1
votes

Pourquoi un élément supplémentaire est-il ajouté à mon tableau void ** lorsque j'utilise le tri par fusion?

Lorsque j'utilise mergeSort pour trier mon tableau void ** (ce tableau contient des pointeurs void * qui pointent vers des entiers), un supplément 1 (un nouvel élément) semble être ajouté au tableau. Je suis presque certain que le problème provient de mergeSort ou merge , comme lorsque j'imprime mon tableau void ** avant d'appeler mergeSort code >, les données sont correctes (juste non triées). Voici le code.

5 6 3 2 5 6 7 4 9 3
1 2 3 3 4 5 5 6 6 7

  La sortie doit avoir le tableau non trié, le tableau trié et si la requête a été trouvée. Il n'y a pas de  1  dans le tableau non trié, mais il y a alors un  1  dans le tableau trié; aussi, le nombre  9  est absent des résultats triés (intéressant, si j'effectue une recherche binaire pour  9 , cela me dira que  9  se trouve à l'index 10).
  Exemple de sortie (pour une requête de 1):
 #define SIZE 10

void mergeSort(void**, int, int);
void merge(void**, int, int, int);
int compare(void*, void*);

int main(void) {
    int array[SIZE] = { 5, 6, 3, 2, 5, 6, 7, 4, 9, 3 };
    void *voidArray[SIZE];
    int query = 1;
    void *queryPointer = &query;

    for (int j = 0; j < SIZE; j++) {
        voidArray[j] = &array[j];
    }

    printArray(voidArray);
    mergeSort(voidArray, 0, SIZE);
    printArray(voidArray);
    result = binarySearch(voidArray, 0, SIZE, queryPointer);

    if (result == -1) {
        puts("Query not found.");
        return(0);
    }

    printf("Query found at index %d.\n", result);
    return(0);
}

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

void mergeSort(void **array, int head, int tail) {
    if (head < tail) {
        int middle = (head + ((tail - head) / 2));
        mergeSort(array, head, middle);
        mergeSort(array, (middle + 1), tail);
        merge(array, head, middle, tail);
    }
}

void merge(void **array, int head, int middle, int tail) {
    int headLength = (middle - head + 1);
    int tailLength =  (tail - middle);
    void *headSide[headLength];
    void *tailSide[tailLength];

    for (int i = 0; i < headLength; i++) {
        headSide[i] = array[head + i];
    }

    for (int j = 0; j < tailLength; j++) {
        tailSide[j] = array[middle + 1 + j];
    }

    int k = head;
    int l = 0;
    int m = 0;
    while (l < headLength && m < tailLength) {
        if (compare(headSide[l], tailSide[m]) == -1) {
            array[k] = headSide[l];
            l++;      
        } else {  
            array[k] = tailSide[m];
            m++;
        }
        k++;
    }

    while (l < headLength) {
        array[k] = headSide[l];
        l++;
        k++;
    }

    while (m < tailLength) {
        array[k] = tailSide[m];
        m++;
        k++;
    }
}

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

int compare(void *index, void *query) {
    if (*((int *)index) == *((int *)query)) {
        return (0);
    }

    if (*((int*)index) > *((int*)query)) {
        return (1);        
    }

    return (-1);
}
  Requête trouvée à l'index 0.

c void-pointers mergesort

2 commentaires

Vous devez décider si vous travaillez avec des intervalles fermés ou semi-ouverts. Au moment où vous les mélangez.

Comme il se trouve, vous devrez passer mergeSort (voidArray, 0, SIZE-1);

3 Réponses :

0
votes

Vérifiez l'indice de votre tableau.

int tailLength =  (tail - middle)

tail est la taille du tableau, je pense que tailLength est incorrect.

1 commentaires

Oui, la queue d'un tableau avec 10 éléments est 9, pas 10 comme je l'avais supposé. Merci pour votre aide!

0
votes

headSide[i] = array[head + i];
headSide[i] is void and array[head + i] is void*

0 commentaires

0
votes

Il y a une certaine confusion dans les arguments de margeSort et merge . Passer l'index du dernier élément de la plage n'est pas idiomatique en C. Il est beaucoup plus simple de passer l'index de l'élément après la fin de la plage, ce qui est cohérent avec le passage de 0 et SIZE int main () : mergeSort (voidArray, 0, SIZE); et result = binarySearch (voidArray, 0, SIZE, queryPointer) ;

Voici une version modifiée avec cette API:

void merge(void **array, int head, int middle, int tail) {
    int headLength = middle - head;
    void *headSide[headLength];

    for (int i = 0; i < headLength; i++) {
        headSide[i] = array[head + i];
    }

    int k = head;
    int l = 0;
    while (l < headLength && middle < tail) {
        if (compare(headSide[l], array[middle]) <= 0) {
            array[k++] = headSide[l++];
        } else {  
            array[k++] = array[middle++];
        }
    }
    while (l < headLength) {
        array[k++] = headSide[l++];
    }
}

Notez cependant que l'allocation des tableaux temporaires headSide et tailSide avec stockage automatique (aka sur la pile ) est risqué pour les grands tableaux. De plus, il n'est pas nécessaire de sauvegarder les éléments de la moitié droite dans tailSide car ils ne seront pas écrasés avant d'être copiés à la position finale. Voici une version plus simple de merge:

void mergeSort(void **array, int head, int tail) {
    if (tail - head > 1) {
        int middle = head + (tail - head) / 2);
        mergeSort(array, head, middle);
        mergeSort(array, middle, tail);
        merge(array, head, middle, tail);
    }
}

void merge(void **array, int head, int middle, int tail) {
    int headLength = middle - head;
    int tailLength = tail - middle;
    void *headSide[headLength];
    void *tailSide[tailLength];

    for (int i = 0; i < headLength; i++) {
        headSide[i] = array[head + i];
    }
    for (int j = 0; j < tailLength; j++) {
        tailSide[j] = array[middle + j];
    }

    int k = head;
    int l = 0;
    int m = 0;
    while (l < headLength && m < tailLength) {
        if (compare(headSide[l], tailSide[m]) <= 0) {
            array[k++] = headSide[l++];
        } else {  
            array[k++] = tailSide[m++];
        }
    }
    while (l < headLength) {
        array[k++] = headSide[l++];
    }
    while (m < tailLength) {
        array[k++] = tailSide[m++];
    }
}

0 commentaires