C Número de comparações realizadas e o Número de trocas realizadas

[PaulaFabiana]

Alguém sabe como faz? a professora pediu mas nunca fiz isso, é para ordenar em quicksort e fazer essas 2 contagem...Segue o meu código

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define TAM 10

void printfVet(int *V, int N)
{
    int i;
    for(i = 0; i < N; i++)
        printf("%2d ",V[i]);
    printf("\n");
}

int particiona(int *V, int inicio, int final )
{
    int esq, dir, pivo, aux;
    esq = inicio;
    dir = final;
    pivo = V[inicio];
    while(esq < dir)
    {
        while(V[esq] <= pivo)
            esq++;
        while(V[dir] > pivo)
            dir--;
        if(esq < dir)
        {
            aux = V[esq];
            V[esq] = V[dir];
            V[dir] = aux;
        }
    }
    V[inicio] = V[dir];
    V[dir] = pivo;
    return dir;
}

void quickSort(int *V, int inicio, int fim)
{
    int pivo;
    if(fim > inicio)
    {
        pivo = particiona(V, inicio, fim);
        quickSort(V, inicio, pivo-1);
        quickSort(V, pivo+1, fim);
    }
}

main()
{
    clock_t tempo;
    tempo = clock();
    int i, Vetor[TAM], j=TAM;

   for(i=0; i<TAM; i++){

    Vetor[i]= j;
    j--;
   }
    for(i= 0; i<TAM; i++)
    printf("%d-", Vetor[i]);
    printf("\n");

    quickSort(Vetor, 0,TAM-1);


    printf("\n Ordernado: \n");
    for(i= 0; i<TAM; i++)
        printf("%d-", Vetor[i]);
    printf("\n\n");


    for( i = 0; i < 99999999; ++i) {}
    printf("Tempo:%f",(clock() - tempo) / (double)CLOCKS_PER_SEC);

}

 

[devair1010]

@PaulaFabiana    seu código está bom,   mas está com erro na função particiona, o pivo precisa ser dividido por 2 , então modifiquei essa parte do código e ele ficou assim :

#include <stdio.h>
#include <conio.h>
#include <time.h>
int comparacao,trocas;
void quicksort(int valores[], int inicio, int fim)
{
    int i, j, pivo, aux;
    i = inicio;
    j = fim-1;
    pivo = valores[(inicio + fim) / 2];
    while(i <= j){
        while(valores[i] < pivo && i < fim)
            i++;
        while(valores[j] > pivo && j > inicio)
            j--;
        comparacao++;
        if(i <= j){
            trocas++;
            aux        = valores[i];
            valores[i] = valores[j];
            valores[j] =        aux;
            i++;
            j--;
        }
    }
    if(j > inicio){
        comparacao++;
        quicksort(valores, inicio, j+1);
    }
    if(i < fim){
        comparacao++;
        quicksort(valores, i, fim);
    }
}
int main()
{
    int i;
    clock_t tempo;
    tempo = clock();
    srand(time(NULL));
    int array[10] = {5, 8, 1, 2, 7, 3, 6, 9, 4, 10};
    printf("Numeros Aleatorios --> ");
    for(i = 0; i < 10; i++){
        array[i]=rand()%10+1;
        printf("%d ",array[i]);
    }
    printf("\n");
    quicksort(array, 0, 10);
    printf("Numeros Ordenadados -> ");
    for(i = 0; i < 10; i++)
        printf("%d ",array[i]);
    for( i = 0; i < 99999999; ++i) {}
    printf("\n\nTempo : -----> %.2f",(clock() - tempo) / (double)CLOCKS_PER_SEC);
    printf("\n\nComparacoes -> %d",comparacao);
    printf("\nTrocas ------> %d\n\n",trocas);
    return 0;
}

 

[PaulaFabiana]

@devair1010 Muito obrigado Devair