Utilizando a função QSort em C

Neste artigo darei uma breve introdução a ponteiros de funções: O que são? Como declará-los? É possível usá-los?. Além disso falaremos de uma função muito mistificada por nós brasileiros, a QSort. A QSort é definida pelo ANSI C e seu nome se deve a utilizar o algoritmo QuickSort.

[ Hits: 105.845 ]

Por: Ricardo Rodrigues Lucca em 30/04/2005 | Blog: http://aventurasdeumdevop.blogspot.com.br/


Programa exemplo



#include <stdlib.h>
#include <stdio.h>

int compara(x, y)
void *x, *y; /* Declaração antiga do ANSI C, mas muito útil */
{
    if ( *(int*)x > *(int*)y )
       return 1;
    else if ( *(int*)x == *(int*)y )
            return 0;
    else if ( *(int*)x < *(int*)y )
            return -1;
}

int main( void )
{
int tamanho = 50;
int *vetor = (int *) malloc(sizeof(int)*tamanho);
int aux;

printf("Construindo vetor de tamanho %d\n", tamanho);
for ( aux = 0; aux < tamanho; aux++ )
    vetor[aux] = random() % tamanho;

printf("Vetor antes da ordenação...\n");
for ( aux = 0; aux < tamanho; aux++ )
    printf("%4d",vetor[aux]);
printf("\n");

qsort( vetor, (size_t) tamanho, sizeof(int), compara );

printf("Vetor depois da ordenação...\n");
for ( aux = 0; aux < tamanho; aux++ )
    printf("%4d",vetor[aux]);
printf("\n");

return EXIT_SUCCESS;
}
Página anterior     Próxima página

Páginas do artigo
   1. Introdução
   2. Ponteiros para funções
   3. QSort
   4. Programa exemplo
   5. Conclusões
Outros artigos deste autor

Conceitos sobre o X-Window

VIM avançado (parte 2)

Introdução as Bibliotecas do C/C++

Como recuperar a senha o root

Analogia: X-Window como um sistema operacional

Leitura recomendada

Introdução a GTK+ em C

Introdução à linguagem C - Parte I

Estudo de ponteiros para GNU/Linux

Funcionamento da memória

Introdução à linguagem C - Parte IV

  
Comentários
[1] Comentário enviado por hunz em 05/06/2005 - 09:24h

Conhecia o quicksort mas não a função qsort, isso facilitou muito para criar os códigos.
Notei que você usou cast dentro da função que compara os valores, tem outro meio de fazer isso (as vezes até mais facil).

A função para comparar você já define como inteiro..
int compara(int *x, int *y)
{
if (*x > *y)
return 1;
else if (*x == *y)
return 0;
else if (*x < *y)
return -1;
}

E na hora de usar o qsort você faz um cast para void* na função...
qsort( vetor, (size_t) tamanho, sizeof(int), (void *) compara );

Abraços,
Fiquem com Deus.

[2] Comentário enviado por FelipeAbella em 10/12/2005 - 16:10h

Eu sempre usei a funcao qsort num banco de dados que eu fiz, eh uma ordenaçao rapida e muito util!

Parabens pelo artigo

[3] Comentário enviado por marcomodesto em 22/06/2006 - 11:34h

Muito bom o artigo. Inclusive aparece na primeira posicao do Google Brasil para a pesquisa qsort. Irei tentar dar mais exemplos uteis para enriquecer o artigo.

A dificuldade que tive com qsort foi ordenar uma estrutura (struct).
Alem disto eu usava uma chave do tipo float para a ordenacao. Como mostrado no exemplo, a comparacao tem que ser um pouco diferente.
Resumindo, no exemplo abaixo, usou-se qsort, structs, typedef e comparacao de floats. Tentei simplifica-lo para ficar didatico.

Quem continuar com duvidas sobre o uso de qsort em structs, recomendo o site abaixo:
http://www.cs.utah.edu/dept/old/texinfo/glibc-manual-0.02/library_8.html

abracos,

Marco Modesto.


#include<stdlib.h>
#include<stdio.h>

#define NUM_DOCS 10

typedef struct {
float W; //Weight
int doc_id; //Document identifier
} TipoItem;

typedef struct {
TipoItem *I;
int doc_p; //Last document pointer
} TipoLista;

void preenche(TipoLista *L){
int i;
TipoItem Aux;
for(i=0; i<NUM_DOCS; i++){
Aux.doc_id = random() % NUM_DOCS;
Aux.W = (float) (random() % NUM_DOCS);
L->I[L->doc_p++] = Aux;
}
}

/* Comparacao para o tipo int (inteiros) */
int compInt (const TipoItem *c1, const TipoItem *c2){
return (c1->doc_id - c2->doc_id);
}

/* Comparacoes para o tipo float (numeros em ponto flutuante) */
//Be careful when comparing floating-point types!!
int compFloat1(const TipoItem *a, const TipoItem *b){
if (b->W - a->W > 0.0)
return 1;
else if (a->W - b->W > 0.0)
return -1;
return 0; //equals
}
//I think the cost of this function is more expensive...
int compFloat2 (const TipoItem *a, const TipoItem *b){
return (10000*(b->W - a->W));
}


int main(){
TipoLista A;
int i, nDocs = NUM_DOCS;

A.I = malloc(nDocs*sizeof(TipoItem));
if (!A.I) {printf ("Erro: Memoria Insuficiente");exit;}

A.doc_p = 0;
preenche(&A);


printf("Antes (numeros aleatorios):\n");
for(i=0; i<NUM_DOCS; i++){
printf("(%d, %.2f)", A.I[i].doc_id, A.I[i].W);
}

//Ordenacao pelo doc_id (int):
qsort (A.I, NUM_DOCS, sizeof (TipoItem), (void *) compInt);
printf("\n\nDepois (Ordenacao pelo doc_id (int)): \n");
for(i=0; i<NUM_DOCS; i++){
printf("(%d, %.2f)", A.I[i].doc_id, A.I[i].W);
}

//Ordenacao pelo W (float):
qsort (A.I, NUM_DOCS, sizeof (TipoItem), (void *) compFloat1);
//OU:
//qsort (A.I, NUM_DOCS, sizeof (TipoItem), (void *) compFloat2);
printf("\n\nDepois (Ordenacao pelo W (float) - ordem decrescente): \n");
for(i=0; i<NUM_DOCS; i++){
printf("(%d, %.2f)", A.I[i].doc_id, A.I[i].W);
}
printf ("\n");

return 0;
}

[4] Comentário enviado por marlls1989 em 04/04/2009 - 13:19h

Só achei sua função de comparação de valores muito ineficiente, para que fazer o processador executar saltos e condicionais se basta faze-lo subtrair.

int compr(int* a, int*b)
{
return *a - *b;
}


Contribuir com comentário