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.861 ]

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


Conclusões



Primeiro de tudo queria pedir desculpas por não dar mais exemplos de ponteiros de funções. O fato é que o artigo tenta desmistificar a função QSort e não como ponteiros de funções funcionam.

Queria aproveitar para falar um pouquinho mais da função que o QSort fica dependente. Quem leu com atenção e é amante do C deve ter notado alguma semelhança com outra função, pois é! É altamente recomendável utilizar strcmp() quando for possível para aliviar o trabalho dos if's.

Quem quiser saber mais consulte as páginas do man.

$ man qsort

Ou visite esses sites:
[]'s

Página anterior    

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

Aprendendo a utilizar o GNU Debugger (parte 1)

Apreendendo a utilizar o GNU Debugger (parte 2)

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

Como recuperar a senha o root

Linux no Rio Grande do Sul

Leitura recomendada

Funcionamento da memória

Criando uma aplicação gráfica com o Qt Designer

Introdução à linguagem C - Parte I

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

Mais sobre recursividade em 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.

[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