Ir para o conteúdo

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 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);