How to implement a generic MergeSort sorting algorithm?

How to implement a generic MergeSort sorting algorithm (with function pointer and void pointer) in this function?

#include<stdio.h>
typedef struct{
    inta;
    intb;
}XPTO;

void criaVetor(XPTO∗v, int n){
    int i;
    for(i=0;i<n;i++){
    v[i].a=i%3;
    v[i].b=100−i%5;
    }
}


void imprimeVetor(XPTO∗v, int n){
    int i;
    for(i=0;i<n;i++){
    printf(”a=%d b=%d\n”,v[i].a,v[i].b);
    }
}

int porA(void ∗p1,void ∗p2){
    XPTO∗pp1=p1;
    XPTO∗pp2=p2;
    return pp1−>a < pp2−>a;
}

int porB(void ∗p1,void ∗p2){
    XPTO∗pp1=p1;
    1XPTO∗pp2=p2;
        returnpp1−>b < pp2−>b;
}


int main(int argc,char∗ argv[]){ 

XPTO v[10];
criaVetor(v,10);

ordena(v,sizeof(XPTO),10,porA);//<−exemplo de chamada da funcao ordena

imprimeVetor(v,10);

return 0;
}
Author: Woss, 2018-06-11
Source

1 answers

I made a solution below.

  1. I used a function pointer to be the comparator (int (*comparador)(void *, void *)). This comparison can return a negative number if the first parameter (the first void *) is less than the second, positive if it is greater, or zero if they are equal.

  2. Mergesort requires an auxiliary memory. For this reason, that there is a malloc and a free in the implementation of the mergesort below. This malloc is only performed once and the same auxiliary memory is used in all recursions of mergesort_aux. The function mergesort_aux is the one that performs mergesort in fact, only receiving as a parameter, the auxiliary memory.

  3. The function memcpy is used to copy from the array to the auxiliary memory and back as well. This is used in the process of interleaving the two halves of the array. The interleaving occurs when copying the elements of each half of the array into the auxiliary memory, in the order of the elements given by the comparator as determined by the mergesort. Thus, the function intercalar will place in the array aux the interleaving of array1 and array2, using memcpy to copy the elements. With another memcpy the interleaved array is copied back over the two original arrays overwriting them.

  4. Although the function mergesort and the comparator work with elements of type void *, internally the char * is used. The reason for this is that it is not possible to perform pointer arithmetic with void *. On the other hand, with char *, it is possible to address any byte individually in the array to be ordered.

  5. I also put a field c in your XPTO with the original position in the array. This serves to show that the ordering of mergesort is stable. That is, elements that the comparator says are equal are kept in the same order as they were in the original array.

Here's the Code: 

#include <stdio.h>
#include <stdlib.h>
#include <string.h> // Para a função memcpy

// Código do mergesort:

void intercalar(
    char *array1,
    char *array2,
    size_t tamanho_array1,
    size_t tamanho_array2,
    char *aux,
    size_t tamanho_elemento,
    int (* comparador)(void *, void *)
) {
    int a = 0, b = 0, c = 0;
    while (a < tamanho_array1 || b < tamanho_array2) {
        int ain = a < tamanho_array1;
        int bin = b < tamanho_array2;
        char *e1 = ain ? &array1[a * tamanho_elemento] : NULL;
        char *e2 = bin ? &array2[b * tamanho_elemento] : NULL;
        char *e3 = &aux[c * tamanho_elemento];
        char *comp = (e2 == NULL || (e1 != NULL && comparador(e1, e2) <= 0)) ? e1 : e2;
        memcpy(e3, comp, tamanho_elemento);
        if (comp == e1) a++; else b++;
        c++;
    }
}

void mergesort_aux(
    char *array,
    char *aux,
    size_t tamanho_elemento,
    size_t tamanho_array,
    int (* comparador)(void *, void *)
) {
    if (tamanho_array < 2) return;
    int metade1 = tamanho_array / 2;
    int metade2 = tamanho_array - metade1;
    mergesort_aux(array, aux, tamanho_elemento, metade1, comparador);
    char *temp = &array[metade1 * tamanho_elemento];
    mergesort_aux(temp, aux, tamanho_elemento, metade2, comparador);
    intercalar(array, temp, metade1, metade2, aux, tamanho_elemento, comparador);
    memcpy(array, aux, tamanho_elemento * tamanho_array);
}

void mergesort(
    void *array,
    size_t tamanho_elemento,
    size_t tamanho_array,
    int (* comparador)(void *, void *)
) {
    void *aux = malloc(tamanho_elemento * tamanho_array);
    mergesort_aux((char *) array, (char *) aux, tamanho_elemento, tamanho_array, comparador);
    free(aux);
}

// Seu código de teste:

typedef struct {
    int a;
    int b;
    int c;
} XPTO;

void criar_vetor(XPTO *v, int n) {
    for (int i = 0; i < n; i++) {
        v[i].a = (i % 3) + 4;
        v[i].b = 100 - i % 5;
        v[i].c = i;
    }
}

void imprimir_vetor(XPTO *v, int n) {
    for (int i = 0; i < n; i++) {
        printf("(a=%d b=%d c=%d) ", v[i].a, v[i].b, v[i].c);
    }
    printf("\n");
}

int por_a(void *p1, void *p2) {
    XPTO *pp1 = (XPTO *) p1;
    XPTO *pp2 = (XPTO *) p2;
    return pp1->a - pp2->a;
}

int por_b(void *p1, void *p2) {
    XPTO *pp1 = (XPTO *) p1;
    XPTO *pp2 = (XPTO *) p2;
    return pp1->b - pp2->b;
}

#define T 20

int main(int argc, char* argv[]) {
    XPTO v[T];
    criar_vetor(v, T);

    printf("Antes:\n");
    imprimir_vetor(v, T);

    printf("\nPor A:\n");
    mergesort(v, sizeof(XPTO), T, por_a);
    imprimir_vetor(v, T);

    criar_vetor(v, T); // Recria o vetor.
    printf("\nPor B:\n");
    mergesort(v, sizeof(XPTO), T, por_b);
    imprimir_vetor(v, T);

    return 0;
}

See here working on ideone.

 0
Author: Victor Stafusa, 2018-06-11 17:59:07