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

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

2 0

Denuncie Favoritos Indicar Impressora

Ponteiros para funções

Antes de entrar em ponteiros de funções, vamos recapitular o básico...

O que é uma variável?
Uma variável é um espaço reservado na memória para seu programa poder usar referenciado por um nome.

O que é uma função?
Uma função é um trecho de código com alguma finalidade...

O que é um ponteiro?
Um ponteiro é uma variável que contém o local de um outro espaço alocado na memória.

A revisão dos conceitos estão sendo "por cima", pois acredito que quem vai ler isso já tenha conhecimento suficiente para seguir adiante...

Uma função é como já dizemos, um trecho de código para alguma finalidade. Esse código fica em algum lugar da memória e sempre que chamamos certa função. É procurado num banco que contém o endereço de todas as funções aninhadas (o C não suporta aninhamento) para aquele nível, esse banco tem entre outras coisas o endereço da função. Assim, o C nós permite recuperar este dado e colocá-lo numa variável, isto é, um ponteiro para função.

Agora que nós já sabemos o que é um ponteiro de função, como vamos declará-lo?

Basicamente a sintaxe de um ponteiro para função segue este estilo:

retorno(*nomedavariavel)(tipoparametro_funcao...)

A partir dessa sintaxe básica podemos ter dois tipos de declaração. Ambas, estão corretas:

int *fsoma;
int (*insere)(char *, void *);

No primeiro caso, no ponteiro para inteiro "fsoma" nós não estamos especificando os parâmetros da função. Mas, isso não causa nenhum problema. Esse fato permite o ponteiro receber uma gama maior de funções, já que não definimos como tem que ser os parâmetros da função.

No segundo caso, temos um ponteiro para função especificando como ficarão os parâmetros da função. Assim, o endereço da função que for alojada ali terá que ter os tipos de parâmetros como os citados, senão o compilador não deixará continuar.

Também podemos ter ponteiros para funções que retornam funções, como é o caso de:

int (*teste)(void)();

int (*seila)() = Soma;

Estamos atribuindo o endereço de Soma() para o apontador de inteiro seila. Agora você deve estar se perguntando, se tenho o endereço da função em algum ponteiro então isso quer dizer que posso chamar a função pelo ponteiro? Sim isso é possível!

No exemplo se fizermos:

(seila)(); //Soma não tem parâmetros

A função Soma() será executada mesmo chamando seila. Mas se tivéssemos algo como:

int *seila = Soma;

Resultaria em erro a tentativa anterior, pois para ele seila é somente um ponteiro para inteiro e não para função. Assim, chegamos a conclusão que o que havíamos dito anteriormente não é verdade. Se quisermos um apontador para inteiro existe somente uma forma, que nesse caso foi a segunda citada.

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

Introdução à linguagem C - Parte III

Linux Básico - Parte I

Introdução à linguagem C - Parte IV

Linux no Rio Grande do Sul

Apreendendo a utilizar o GNU Debugger (parte 2)

Leitura recomendada

Estudo de ponteiros para GNU/Linux

Liberando Memória ajustando o Tamanho das Strings em C

Criando uma calculadora com o KDevelop

Introdução à linguagem C - Parte III

Operadores com a linguagem 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