How to implement a generic MergeSort sorting algorithm?

Question

How to implement a generic MergeSort sorting algorithm?

Navigation

#1 by (0 votes)

0

How to implement a generic MergeSort generic sort 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;
}

c ponteiro

asked by anonymous 11.06.2018 / 14:32

1 answer

Same header and footer for multiple sites How to install the FFTW3 library for android?

score 0 · Answer 1

I made a workaround below.

I used a function pointer to be the comparator ( int (*comparador)(void *, void *) ). This compared 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.

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

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

Although the mergesort function and the comparator work with elements of type void * , internally 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 single byte in the array to be sorted.

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

Here is 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.