Utilizando a função QSort em C

jllucca

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: 111.983 ]

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

2 0

Denuncie Favoritos Indicar Impressora

QSort

Agora que já falamos sobre ponteiros de funções, estamos preparados para ver o protótipo da função QSort:

void qsort( void *base, size_t quantidade, size_t tamanho, int(*compar)(const void *, const void *) );

A função QSort, como já falamos, serve para ordenar coisas. A função para manter seu nível de abstração o mais alto possível adotou uma saída inteligente para saber como ordenar as coisas sem se preocupar com isso. A solução está no último parâmetro:

int(*compar)(const void *, const void *)

A função QSort é dependente de outra função e esta é criada pelo programador. A única coisa que temos que ter em mente é que a função retornará um inteiro e receberá dois parâmetros do tipo void.

Voltando ao QSort, o primeiro parâmetro recebe a base do nosso vetor, em seguida temos de dizer a quantidade de elementos existentes no vetor. Nosso terceiro parâmetro é o tamanho de cada elemento do vetor, seguido por um ponteiro para função.

A função que o ponteiro para função apontar será chamada sempre com dois elementos e seu retorno ditará se os elementos serão trocados de lugar ou não. Para ficar mais claro, os valores de retorno para o QSort são:

Se o primeiro for maior que o segundo deve retornar um número maior que zero;
Se o primeiro for menor que o segundo deve retornar um valor menor que zero;
Se forem iguais então retorna zero.

Baseado nisso, temos uma função chamada "compara" para ser utilizada por QSort no nosso exemplo. O QSort sempre irá ordenar os vetores em ordem ascendente, mas podemos aproveitar de sua dependência da função externa e ao inverter a lógica usada, ordenar de forma descendente. Isto torna possível o programador escolher se a ordenação será do maior pro menor ou do menor pro maior. Além disso, como QSort lida com qualquer dado, seria impossível de automatizar uma tarefa dessas.

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

Criando um servidor de Ultima Online

Ponteiros void na linguagem C (parte 2)

Analogia: X-Window como um sistema operacional

Conceitos sobre o X-Window

Uma pequena análise do Gentoo Linux

Leitura recomendada

Liberando Memória ajustando o Tamanho das Strings em C

Introdução à linguagem C - Parte I

O ? Alternativo em C/C++

Estudo de ponteiros para GNU/Linux

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

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.

0 0

[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

0 0

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

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

1 0