0

Como implementar um algoritmo de ordenação MergeSort genérico (com ponteiro de função e ponteiro void) nessa função?

#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;
}
2
  • 1
    Sugiro que comece pelo mais simples mesmo. Comece por implementar um que funcione para inteiros por exemplo e depois então converta-o para genérico. Comece também por ler como o algoritmo funciona e fazer a sua tentativa de resolução. A maior parte das literaturas incluem exemplos do algoritmo em pseudo código que facilitam-lhe a implementação.
    – Isac
    Commented 11/06/2018 às 12:48
  • Have you tried turning it off and on again?
    – Woss
    Commented 11/06/2018 às 13:03

1 Resposta 1

1

Fiz uma solução abaixo.

  1. Utilizei um ponteiro de função para ser o comparador (int (*comparador)(void *, void *)). Esse comparado pode retornar um número negativo se o primeiro parâmetro (o primeiro void *) for menor que o segundo, positivo se for maior, ou zero se forem iguais.

  2. O mergesort necessita de uma memória auxiliar. Por esse motivo, que há um malloc e um free na implementação do mergesort abaixo. Esse malloc só é efetuado uma vez e a mesma memória auxiliar é usada em todas as recursões do mergesort_aux. A função mergesort_aux é a que realiza o mergesort de fato, apenas recebendo como parâmetro, a memória auxiliar.

  3. A função memcpy é utilizada para copiar do array para a memória auxiliar e de volta também. Isso é usado no processo de intercalação das duas metades do array. A intercalação ocorre ao copiar-se os elementos de cada metade do array na memória auxiliar, na ordem dos elementos dada pelo comparador tal como determina o algoritmo de mergesort. Assim, a função intercalar vai colocar no array aux a intercalação de array1 e array2, usando memcpy para copiar os elementos. Com um outro memcpy o array intercalado é copiado de volta por cima dos dois arrays originais sobreescrevendo-os.

  4. Embora a função mergesort e o comparador trabalhem com elementos do tipo void *, internamente o char * é usado. O motivo disso é que não é possível realizar-se aritmética de ponteiros com void *. Por outro lado, com char *, é possível endereçar-se qualquer byte individualmente no array a ser ordenado.

  5. Também coloquei um campo c no seu XPTO com a posição original no array. Isso serve para evidenciar que a ordenação do mergesort é estável. Ou seja, elementos que o comparador diz que são iguais são mantidos na mesma ordem em que estavam no array original.

Eis o código:

#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;
}

Veja aqui funcionando no ideone.

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .