Ferramentas de Usuário

Ferramentas de Site


dev_geral:c:c_qsort

C: O qsort - Ordenar listas e matrizes

Neste tutorial vamos ver como ordenar listas e matrizes usando o qsort.

O qsort é uma função que se encontra na biblioteca standard do C, na "stdlib.h".

void qsort(void *dados, int n_blocos, int t_blocos, int (*comparar)(const void * a, const void * b));

dados

É o primeiro argumento a ser passado para a função é um ponteiro para os dados que queremos ordenar.

n_blocos

É o número de "blocos" que queremos ordenar.

t_blocos

O tamanho de cada bloco. Por exemplo:

int matriz[x][y];
int tamanho;
 
tamanho = sizeof(*matriz);
//ou
tamanho = sizeof(int)*y

comparar

O quarto argumento é uma função que recebes dois argumentos (A e B), que são dois ponteiros "const void", compara-os e retorna um valor inteiro em função da sua diferença.

A função qsort vai ordenar de forma crescente, por isso os valores retornados têm de ser e acordo com o que nós pretendemos. Se o valor retornado for:

  • Menor que 0 - significa que o B é maior que o A, logo o B vai ser posicionado depois do A;
  • Igual a 0 - significa que os dois valores são iguais;
  • Maior que 0 - significa que A maior que B, logo o A será posicionado depois de B.

Antenção o valor retornado tem de ser um int!

Exemplo:

int comparar(const void* a, const void* b){
    if(*(int*)a-*(int*)b>0)
        return 1;
    if(*(int*)a-*(int*)b<0)
        return -1;
    return 0;
}

Deve de se substituir o int pelo tipo de dados que estamos a comparar, ou seja pelo tipo de dados a lista/matriz. Caso o tipo de dados seja int a função pode ser simplificada, ficando assim:

int comparar(const void* a, const void* b){
    return *(int*)a-*(int*)b;
}

Este exemplo ordenda os dados de forma crescente, se quizermos por ordenar por ordem decrescente basta alterar a ordem da comparação:

int comparar(const void* a, const void* b){
    return *(int*)b-*(int*)a;
}

Ordenar uma lista

Ordenar uma lista de long long ints de forma crescente:

#include <stdlib.h>
 
int n=5;
long long int lista[n]={64564648868, 3, 6448868, 8, 15};
 
int compara_crescente(const void* a, const void* b){
    if(*(long long int*)a-*(long long int*)b>0)
        return 1;
    if(*(long long int*)a-*(long long int*)b<0)
        return -1;
    return 0;
}
 
qsort(lista, n, sizeof(*lista), compara_crescente);
dev_geral/c/c_qsort.txt · Última modificação em: 2018/05/14 21:37 (edição externa)