Counters in the Mergesort

Question

I would like to know where I need to insert my variables that count exchanges and comparisons.

In this algorithm I am dealing with an array of two positions that by reference modify details[0] that would be the amount of comparisons and details[1] that would be the amount of exchanges.

I don’t know where to insert and I’ve done research and more research and no one can answer that question. Thank you if you can answer me. Hugs.

void merge(int *array, int inicio, int meio, int fim, unsigned long int *detalhes){

    int *vetAux, p1, p2, tamanho, i, j, k;
    int fim1 = 0, fim2 = 0;
    tamanho = fim - inicio + 1;
    p1 = inicio;
    p2 = meio + 1;
    vetAux = (int *) malloc(tamanho * sizeof(int));

    if(vetAux != NULL){
        for(i = 0; i < tamanho; i++){
            if(!fim1 && !fim2){
                detalhes[0]++;
                if(array[p1] < array[p2]){
                    vetAux[i] = array[p1++];
                    detalhes[1]++;
                }
                else{
                    vetAux[i] = array[p2++];
                    detalhes[1]++;
                }
                if(p1 > meio)
                    fim = 1;
                if(p2 > fim)
                    fim2 = 1;
            } else {
                detalhes[0]++;
                if(!fim1){
                    vetAux[i] = array[p1++];
                    detalhes[1]++;
                }
                else{
                    vetAux[i] = array[p2++];
                    detalhes[1]++;
                }
            }
        }
        for(j = 0, k = inicio; j < tamanho; j++, k++){
            array[k] = vetAux[j];
        }

    }
    free(vetAux);
}

void mergeSort(int *array, int inicio, int fim, unsigned long int *detalhes){
    int meio;
    if(inicio < fim){
        meio = floor((fim + inicio)/2);
        mergeSort(array, inicio, meio, detalhes);
        mergeSort(array, meio+1, fim, detalhes);
        merge(array, inicio, meio, fim, detalhes);
    }
}

Vector statement of details in main():

unsigned long int detalhes[2] = {0};

Calling the sort function in main():

detalhes[0] = 0; detalhes[1] = 0;
tempo[0] = clock();
mergeSort(array, inicio, fim, detalhes);
tempo[1] = clock();
showDetalhes(detalhes, array, size, tempo);

Note: These variables are in the wrong places, because the results are not coming out right.

Answer 1

You can create a structure to encapsulate your counters, see:

typedef struct detalhes_s
{
    int comps;                /* Quantidade de comparacoes */
    int trocas;               /* Quantidade de trocas */
    unsigned long duracao_us; /* Tempo total de processamento em microsegundos */
} detalhes_t;

With some modifications, its sorting functions would look something like this:

void merge( int *array, int inicio, int meio, int fim, detalhes_t *detalhes )
{
    int *vetAux, p1, p2, tamanho, i, j, k;
    int fim1 = 0, fim2 = 0;
    tamanho = fim - inicio + 1;
    p1 = inicio;
    p2 = meio + 1;

    vetAux = (int *) malloc( tamanho * sizeof(int) );

    if(vetAux != NULL){
        for(i = 0; i < tamanho; i++){
            if(!fim1 && !fim2){
                detalhes->comps++;
                if(array[p1] < array[p2]){
                    vetAux[i] = array[p1++];
                    detalhes->trocas++;
                }
                else{
                    vetAux[i] = array[p2++];
                    detalhes->trocas++;
                }
                if(p1 > meio)
                    fim = 1;
                if(p2 > fim)
                    fim2 = 1;
            } else {
                detalhes->comps++;
                if(!fim1){
                    vetAux[i] = array[p1++];
                    detalhes->trocas++;
                }
                else{
                    vetAux[i] = array[p2++];
                    detalhes->trocas++;
                }
            }
        }

        for(j = 0, k = inicio; j < tamanho; j++, k++){
            array[k] = vetAux[j];
        }
    }

    free(vetAux);
}

void mergeSortR(int *array, int inicio, int fim, detalhes_t *detalhes )
{
    int meio;
    if(inicio < fim) {
        meio = floor( (fim + inicio) / 2 );
        mergeSortR( array, inicio, meio, detalhes );
        mergeSortR( array, meio+1, fim, detalhes );
        merge( array, inicio, meio, fim, detalhes );
    }
}

void mergeSort(int *array, int inicio, int fim, detalhes_t *detalhes )
{
    struct timeval t0, t1;

    /* Inicializa estrutura de detalhes */
    detalhes->comps = 0;
    detalhes->trocas = 0;

    gettimeofday(&t0, NULL);
    mergeSortR( array, inicio, fim, detalhes );
    gettimeofday(&t1, NULL);

    /* Calcula tempo de processamento */
    detalhes->duracao_us = ((t1.tv_sec - t0.tv_sec) * 1000000L) + (t1.tv_usec - t0.tv_usec);
}

Testing everything:

#include <stdlib.h>
#include <stdio.h>
#include <math.h>
#include <time.h>
#include <sys/time.h>

typedef struct detalhes_s
{
    int comps;                /* Quantidade de comparacoes */
    int trocas;               /* Quantidade de trocas */
    unsigned long duracao_us; /* Tempo total de processamento em microsegundos */
} detalhes_t;

void merge( int *array, int inicio, int meio, int fim, detalhes_t *detalhes )
{
    int *vetAux, p1, p2, tamanho, i, j, k;
    int fim1 = 0, fim2 = 0;
    tamanho = fim - inicio + 1;
    p1 = inicio;
    p2 = meio + 1;

    vetAux = (int *) malloc( tamanho * sizeof(int) );

    if(vetAux != NULL){
        for(i = 0; i < tamanho; i++){
            if(!fim1 && !fim2){
                detalhes->comps++;
                if(array[p1] < array[p2]){
                    vetAux[i] = array[p1++];
                    detalhes->trocas++;
                }
                else{
                    vetAux[i] = array[p2++];
                    detalhes->trocas++;
                }
                if(p1 > meio)
                    fim = 1;
                if(p2 > fim)
                    fim2 = 1;
            } else {
                detalhes->comps++;
                if(!fim1){
                    vetAux[i] = array[p1++];
                    detalhes->trocas++;
                }
                else{
                    vetAux[i] = array[p2++];
                    detalhes->trocas++;
                }
            }
        }

        for(j = 0, k = inicio; j < tamanho; j++, k++){
            array[k] = vetAux[j];
        }
    }

    free(vetAux);
}

void mergeSortR(int *array, int inicio, int fim, detalhes_t *detalhes )
{
    int meio;
    if(inicio < fim) {
        meio = floor( (fim + inicio) / 2 );
        mergeSortR( array, inicio, meio, detalhes );
        mergeSortR( array, meio+1, fim, detalhes );
        merge( array, inicio, meio, fim, detalhes );
    }
}

void mergeSort(int *array, int inicio, int fim, detalhes_t *detalhes )
{
    struct timeval t0, t1;

    /* Inicializa estrutura de detalhes */
    detalhes->comps = 0;
    detalhes->trocas = 0;

    gettimeofday(&t0, NULL);
    mergeSortR( array, inicio, fim, detalhes );
    gettimeofday(&t1, NULL);

    /* Calcula tempo de processamento */
    detalhes->duracao_us = ((t1.tv_sec - t0.tv_sec) * 1000000L) + (t1.tv_usec - t0.tv_usec);
}

int main( void )
{
    unsigned int i;
    detalhes_t info;

    /* Vetor */
    int foobar[16] = { 10, 2, 5, 8, 9, 7, 1, 3, 4, 6, 0, 5, 1, 8, 6, 5 };

    /* Exibe Vetor de entrada */
    for( i = 0; i < sizeof(foobar) / sizeof(int); i++ )
        printf( (i==0) ? "Entrada=%d" :  ",%d", foobar[i] );
    printf("\n");

    /* Ordena vetor */
    mergeSort( foobar, 0, 15, &info );

    /* Exibe vetor ordenado */
    for( i = 0; i < sizeof(foobar)/ sizeof(int); i++ )
        printf( (i==0) ? "Saida=%d" : ",%d", foobar[i] );
    printf("\n");

    /* Exibe Informacoes */
    printf( "Comparacoes: %d\n", info.comps );
    printf( "Trocas: %d\n", info.trocas );
    printf( "Duracao: %ldus\n", info.duracao_us);

    return 0;
}

Exit:

Entrada=10,2,5,8,9,7,1,3,4,6,0,5,1,8,6,5
Saida=0,1,1,2,3,4,5,5,5,6,6,1,7,8,9,10
Comparacoes: 64
Trocas: 64
Duracao: 149us

See working on Repl.it