C Ordenação (qsort)

Ordenar é pôr em ordem: as notas da turma da maior para a menor, os nomes em ordem alfabética, os produtos do mais barato ao mais caro. É uma das tarefas mais comuns da programação, e também a base para procurar depressa. Nesta aula você vai ordenar à mão uma vez, para entender o que acontece por dentro, e depois usar o qsort da biblioteca padrão para ordenar qualquer coisa: números, textos e structs, com o critério que você quiser.

Esta aula continua a aula Ponteiros para Funções, que apresentou o qsort, e usa ponteiro void* e structs e ponteiros. Todos os programas foram compilados com o gcc 15.2 na máquina fictícia da Ana (usuária ana, computador notebook), na pasta ~/c, com o comando padrão do guia: gcc -std=c23 -Wall -Wextra arquivo.c -o programa.

A ideia: as cartas na mão

A Ana está jogando baralho e recebe as cartas uma de cada vez. A cada carta nova, ela a encaixa no lugar certo entre as que já estão na mão: passa pelas maiores, empurrando-as um pouco para o lado, até achar uma menor. A mão está sempre em ordem, e no fim todas as cartas estão ordenadas.

Qualquer jeito de ordenar, por mais esperto que seja, se resume a duas operações: comparar dois itens ("qual vem antes?") e mudar itens de lugar. O que muda de um algoritmo para outro é quais pares ele compara e quantas vezes.

1. Ordenar à mão: a inserção

O jeito da Ana tem nome: ordenação por inserção (insertion sort). Em C, a "mão" é o começo do array, que já está ordenado, e a "carta nova" é o próximo item:

#include <stdio.h>

void mostrar(const int *v, int n) {
    for (int i = 0; i < n; i++) {
        printf(" %d", v[i]);
    }
    printf("\n");
}

void ordenar_insercao(int *v, int n) {
    for (int i = 1; i < n; i++) {
        int carta = v[i];
        int j = i - 1;
        while (j >= 0 && v[j] > carta) {
            v[j + 1] = v[j];
            j--;
        }
        v[j + 1] = carta;
        printf("depois de encaixar o %2d:", carta);
        mostrar(v, n);
    }
}

int main(void) {
    int cartas[] = {7, 3, 10, 5, 9, 1};
    int n = sizeof cartas / sizeof cartas[0];
    printf("no começo:              ");
    mostrar(cartas, n);
    ordenar_insercao(cartas, n);
    return 0;
}

$ gcc -std=c23 -Wall -Wextra insercao.c -o insercao
$ ./insercao
no começo:               7 3 10 5 9 1
depois de encaixar o  3: 3 7 10 5 9 1
depois de encaixar o 10: 3 7 10 5 9 1
depois de encaixar o  5: 3 5 7 10 9 1
depois de encaixar o  9: 3 5 7 9 10 1
depois de encaixar o  1: 1 3 5 7 9 10

for (int i = 1; i < n; i++)

Começa no segundo item: um array de um item só (o v[0]) já está ordenado. A cada volta, v[0] a v[i - 1] é a "mão" ordenada.

int carta = v[i];

Guarda a carta nova, porque a posição dela vai ser ocupada por quem andar para a direita.

while (j >= 0 && v[j] > carta)

Enquanto houver carta na mão e ela for maior que a nova, continua procurando para a esquerda. O j >= 0 vem antes: se j for -1, o && para ali e v[-1] nunca é lido (veja Operadores Lógicos).

v[j + 1] = v[j]; j--;

Empurra a carta maior uma casa para a direita e olha a próxima à esquerda.

v[j + 1] = carta;

Achou o lugar: logo depois da primeira carta que não é maior. Encaixa ali.

Repare no "encaixar o 1": ele é o menor de todos, então todas as outras cinco cartas andaram uma casa. A inserção é ótima para arrays pequenos ou quase ordenados, mas, num array grande e bagunçado, cada carta nova pode empurrar quase todas as anteriores. Com o dobro de itens, o trabalho fica quatro vezes maior. A seção 6 mede isso.

2. O qsort: a ordenação pronta

A biblioteca padrão já tem uma ordenação rápida e testada: o qsort, de <stdlib.h>. O nome vem de quicksort ("ordenação rápida"), o algoritmo das primeiras versões; hoje cada biblioteca usa o algoritmo que quiser, e o padrão do C só promete que o array termina ordenado. O que torna o qsort especial é que ele ordena arrays de qualquer tipo:

#include <stdio.h>
#include <stdlib.h>

int crescente(const void *a, const void *b) {
    int x = *(const int *)a;
    int y = *(const int *)b;
    return (x > y) - (x < y);
}

int main(void) {
    int notas[] = {7, 3, 10, 5, 9, 1, 8};
    size_t n = sizeof notas / sizeof notas[0];

    qsort(notas, n, sizeof notas[0], crescente);

    for (size_t i = 0; i < n; i++) {
        printf("%d ", notas[i]);
    }
    printf("\n");
    return 0;
}

$ gcc -std=c23 -Wall -Wextra qsort_int.c -o qsort_int
$ ./qsort_int
1 3 5 7 8 9 10

O protótipo, como está no stdlib.h, é: void qsort(void *base, size_t n, size_t tamanho, int (*comparar)(const void *, const void *));

3. A função de comparação

O qsort entrega à sua função os endereços de dois itens do array, a e b, como const void *. A função devolve um int que segue uma regra fixa:

int crescente(const void *a, const void *b)

A forma é obrigatória: dois const void * e retorno int. O const promete que a comparação só lê, sem mudar os itens.

int x = *(const int *)a;

Converte o void * para o tipo verdadeiro dos itens (const int *) e lê o valor com o *. Sem a conversão, o C não saberia quantos bytes ler.

return (x > y) - (x < y);

Uma comparação em C vale 1 (verdadeiro) ou 0 (falso). Se x > y: 1 - 0 = 1. Se x < y: 0 - 1 = -1. Se iguais: 0 - 0 = 0. É o mesmo que os dois if da aula Ponteiros para Funções, numa linha.

Três jeitos de escrever, e um que parece certo

Para inverter a ordem (do maior para o menor), troque x e y de lugar: return (y > x) - (y < x);. O qsort é o mesmo; só o critério mudou.

Ordenar double

Para outros tipos, a receita é a mesma: converta para o ponteiro do tipo certo e compare. Com double, a forma (x > y) - (x < y) é ainda mais importante, porque x - y daria um double como 0,3, que, devolvido como int, vira 0 ("tanto faz").

0.75 3.50 5.99 18.90 25.90

#include <stdio.h>
#include <stdlib.h>

int crescente(const void *a, const void *b) {
    // COMPLETE: converta a e b para ponteiros de double, leia os dois valores
    // e devolva negativo, zero ou positivo, como no crescente dos inteiros
    (void)a;
    (void)b;
    return 0;
}

int main(void) {
    double precos[] = {25.90, 0.75, 18.90, 3.50, 5.99};
    size_t n = sizeof precos / sizeof precos[0];

    qsort(precos, n, sizeof precos[0], crescente);

    for (size_t i = 0; i < n; i++) {
        printf("%.2f ", precos[i]);
    }
    printf("\n");
    return 0;
}

#include <stdio.h>
#include <stdlib.h>

int crescente(const void *a, const void *b) {
    double x = *(const double *)a;
    double y = *(const double *)b;
    return (x > y) - (x < y);
}

int main(void) {
    double precos[] = {25.90, 0.75, 18.90, 3.50, 5.99};
    size_t n = sizeof precos / sizeof precos[0];

    qsort(precos, n, sizeof precos[0], crescente);

    for (size_t i = 0; i < n; i++) {
        printf("%.2f ", precos[i]);
    }
    printf("\n");
    return 0;
}

4. Ordenar textos

Textos se comparam com strcmp (aula Funções de String), que já segue a regra do qsort: negativo se o primeiro vem antes no alfabeto, zero se iguais, positivo se vem depois. A pegadinha é o que o qsort entrega para a sua função, e isso depende de como os textos estão guardados.

Um array de ponteiros: const char *turma[]

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int por_nome(const void *a, const void *b) {
    const char *x = *(const char *const *)a;
    const char *y = *(const char *const *)b;
    return strcmp(x, y);
}

int main(void) {
    const char *turma[] = {"Rui", "Ana", "Lia", "Bruno", "Davi", "Ana Clara"};
    size_t n = sizeof turma / sizeof turma[0];

    qsort(turma, n, sizeof turma[0], por_nome);

    for (size_t i = 0; i < n; i++) {
        printf("%s\n", turma[i]);
    }
    return 0;
}

$ gcc -std=c23 -Wall -Wextra nomes.c -o nomes
$ ./nomes
Ana
Ana Clara
Bruno
Davi
Lia
Rui

const char *turma[]

Cada item do array é um ponteiro para um texto. É isso que o qsort ordena: os ponteiros mudam de lugar, os textos ficam onde estão.

*(const char *const *)a

O qsort entrega o endereço de um item. Como cada item é um const char *, a é, na verdade, um ponteiro para ponteiro (const char *const *; aula Ponteiro para Ponteiro). O * da frente lê o item: o ponteiro para o texto.

strcmp(x, y)

Agora sim, compara os dois textos. "Ana" vem antes de "Ana Clara" porque é um pedaço dela: o texto mais curto termina primeiro.

Um array de textos: char turma[][12]

Se os textos estiverem guardados dentro do array (um array de duas dimensões), cada item já é o texto, e o qsort entrega o endereço do primeiro caractere dele:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int por_nome(const void *a, const void *b) {
    return strcmp((const char *)a, (const char *)b);
}

int main(void) {
    char turma[][12] = {"Rui", "Ana", "Lia", "Bruno", "Davi", "Ana Clara"};
    size_t n = sizeof turma / sizeof turma[0];

    qsort(turma, n, sizeof turma[0], por_nome);

    for (size_t i = 0; i < n; i++) {
        printf("%s\n", turma[i]);
    }
    printf("Cada item tem %zu bytes\n", sizeof turma[0]);
    return 0;
}

$ gcc -std=c23 -Wall -Wextra nomes_matriz.c -o nomes_matriz
$ ./nomes_matriz
Ana
Ana Clara
Bruno
Davi
Lia
Rui
Cada item tem 12 bytes

Aqui a já aponta para o texto, então basta strcmp(a, b), sem o * extra. E o qsort troca de lugar os 12 bytes de cada nome, não um ponteiro. O resultado é o mesmo; a função de comparação é diferente:

5. Ordenar structs e desempatar

Com structs, a função de comparação escolhe o campo que decide a ordem. O ranking da turma da Ana: maior nota primeiro e, entre notas iguais, ordem alfabética:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct {
    char nome[20];
    int nota;
} Aluno;

int ranking(const void *a, const void *b) {
    const Aluno *x = a;
    const Aluno *y = b;
    if (x->nota != y->nota) {
        return (y->nota > x->nota) - (y->nota < x->nota);
    }
    return strcmp(x->nome, y->nome);
}

int main(void) {
    Aluno turma[] = {
        {"Rui", 7}, {"Lia", 9}, {"Bruno", 7}, {"Ana", 10},
        {"Davi", 9}, {"Caio", 5}, {"Bia", 7},
    };
    size_t n = sizeof turma / sizeof turma[0];

    qsort(turma, n, sizeof turma[0], ranking);

    for (size_t i = 0; i < n; i++) {
        printf("%zuº %-6s %2d\n", i + 1, turma[i].nome, turma[i].nota);
    }
    return 0;
}

$ gcc -std=c23 -Wall -Wextra alunos.c -o alunos
$ ./alunos
1º Ana    10
2º Davi    9
3º Lia     9
4º Bia     7
5º Bruno   7
6º Rui     7
7º Caio    5

const Aluno *x = a;

Em C, um void * vira outro ponteiro sozinho, sem cast (aula Ponteiro void*). Daí em diante, x->nota e x->nome.

if (x->nota != y->nota)

O primeiro critério: a nota. Se forem diferentes, ela decide sozinha.

(y->nota > x->nota) - (y->nota < x->nota)

Com y na frente: ordem decrescente (maior nota primeiro).

return strcmp(x->nome, y->nome);

O desempate: só chega aqui com notas iguais. Davi e Lia (9) e Bia, Bruno e Rui (7) saíram em ordem alfabética.

%zuº

O %zu é o formato do size_t (veja Formatos do printf); o º é só texto.

Sem desempate: o qsort não é estável

Uma ordenação é estável quando itens empatados continuam na ordem em que estavam. O padrão do C não promete que o qsort seja estável, e cada biblioteca faz de um jeito. Este programa ordena só pela nota uma turma em que todos estão em ordem alfabética:

#include <stdio.h>
#include <stdlib.h>

typedef struct {
    char nome[8];
    int nota;
} Aluno;

int por_nota(const void *a, const void *b) {
    const Aluno *x = a;
    const Aluno *y = b;
    return (x->nota > y->nota) - (x->nota < y->nota);
}

int main(void) {
    Aluno turma[] = {
        {"Ana", 8}, {"Bia", 6}, {"Caio", 8}, {"Davi", 6}, {"Edu", 8},
        {"Fabi", 6}, {"Gil", 8}, {"Hugo", 6}, {"Iris", 8}, {"Joao", 6},
    };
    size_t n = sizeof turma / sizeof turma[0];
    qsort(turma, n, sizeof turma[0], por_nota);
    for (size_t i = 0; i < n; i++) {
        printf("%s(%d) ", turma[i].nome, turma[i].nota);
    }
    printf("\n");
    return 0;
}

$ gcc -std=c23 -Wall -Wextra estavel.c -o estavel
$ ./estavel
Bia(6) Davi(6) Fabi(6) Hugo(6) Joao(6) Ana(8) Caio(8) Edu(8) Gil(8) Iris(8)

No gcc da Ana (com a glibc, a biblioteca C do Linux), os empatados mantiveram a ordem alfabética de antes. Agora rode o mesmo programa no editor do guia, que usa outra biblioteca C (a wasi-libc, baseada na musl):

#include <stdio.h>
#include <stdlib.h>

typedef struct {
    char nome[8];
    int nota;
} Aluno;

int por_nota(const void *a, const void *b) {
    const Aluno *x = a;
    const Aluno *y = b;
    return (x->nota > y->nota) - (x->nota < y->nota);
}

int main(void) {
    Aluno turma[] = {
        {"Ana", 8}, {"Bia", 6}, {"Caio", 8}, {"Davi", 6}, {"Edu", 8},
        {"Fabi", 6}, {"Gil", 8}, {"Hugo", 6}, {"Iris", 8}, {"Joao", 6},
    };
    size_t n = sizeof turma / sizeof turma[0];
    qsort(turma, n, sizeof turma[0], por_nota);
    for (size_t i = 0; i < n; i++) {
        printf("%s(%d) ", turma[i].nome, turma[i].nota);
    }
    printf("\n");
    return 0;
}

Nenhuma das duas está errada: para o critério "nota", empatados são iguais, e o qsort pode pô-los em qualquer ordem. A lição é: se a ordem dos empatados importa, ela precisa estar na função de comparação. Um bom critério de desempate é um campo que não se repete (o nome, uma matrícula). Assim, o resultado é o mesmo em qualquer computador.

Ordenar só um pedaço

Como o qsort recebe um endereço e uma quantidade, dá para ordenar só uma parte do array: passe o endereço do primeiro item do pedaço (aritmética de ponteiros) e quantos itens ele tem.

#include <stdio.h>
#include <stdlib.h>

int crescente(const void *a, const void *b) {
    int x = *(const int *)a;
    int y = *(const int *)b;
    return (x > y) - (x < y);
}

int main(void) {
    int v[] = {9, 8, 7, 6, 5, 4, 3};
    qsort(v + 2, 3, sizeof v[0], crescente);
    for (int i = 0; i < 7; i++) {
        printf("%d ", v[i]);
    }
    printf("\n");
    return 0;
}

$ gcc -std=c23 -Wall -Wextra parte.c -o parte
$ ./parte
9 8 5 6 7 4 3

v + 2 é o endereço do v[2]; com 3 itens, só v[2], v[3] e v[4] (o 7, o 6 e o 5) foram ordenados. O resto ficou como estava.

6. Quanto tempo leva

Este programa ordena os mesmos 100 mil números duas vezes, com a inserção da seção 1 e com o qsort, e mede o tempo de cada uma com clock() (aula Data e Hora). Os números vêm de um sorteador próprio, para serem os mesmos a cada execução:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

int crescente(const void *a, const void *b) {
    int x = *(const int *)a;
    int y = *(const int *)b;
    return (x > y) - (x < y);
}

void ordenar_insercao(int *v, int n) {
    for (int i = 1; i < n; i++) {
        int carta = v[i];
        int j = i - 1;
        while (j >= 0 && v[j] > carta) {
            v[j + 1] = v[j];
            j--;
        }
        v[j + 1] = carta;
    }
}

int main(void) {
    const int n = 100000;
    int *a = malloc(n * sizeof *a);
    int *b = malloc(n * sizeof *b);
    if (a == NULL || b == NULL) {
        free(a);
        free(b);
        return 1;
    }
    unsigned int semente = 42;
    for (int i = 0; i < n; i++) {
        semente = semente * 1103515245u + 12345u;
        a[i] = (int)(semente / 65536u % 1000000u);
    }
    memcpy(b, a, n * sizeof *a);

    clock_t t0 = clock();
    ordenar_insercao(a, n);
    clock_t t1 = clock();
    qsort(b, n, sizeof *b, crescente);
    clock_t t2 = clock();

    printf("inserção: %.3f s\n", (double)(t1 - t0) / CLOCKS_PER_SEC);
    printf("qsort:    %.3f s\n", (double)(t2 - t1) / CLOCKS_PER_SEC);
    printf("iguais? %s\n", memcmp(a, b, n * sizeof *a) == 0 ? "sim" : "não");
    free(a);
    free(b);
    return 0;
}

$ gcc -std=c23 -Wall -Wextra tempo.c -o tempo
$ ./tempo
inserção: 7.738 s
qsort:    0.019 s
iguais? sim

O mesmo resultado (iguais? sim, conferido com memcmp), umas 400 vezes mais depressa. Os tempos mudam de um computador para outro, mas a diferença continua enorme. A inserção compara cada número com uma boa parte dos anteriores: com 100 mil números, são bilhões de comparações. Os algoritmos do qsort (quicksort, mergesort e parentes) dividem o array em pedaços e precisam só de uns 2 milhões. (No editor do guia este programa passa do limite de 15 segundos; deixe-o para o terminal.)

Formas diferentes e qual usar

Quando dá errado

int crescente(const int *a, const int *b) {
    return (*a > *b) - (*a < *b);
}
…
    qsort(notas, 5, sizeof notas[0], crescente);

$ gcc -std=c23 -Wall -Wextra assinatura.c -o assinatura
assinatura.c: In function ‘main’:
assinatura.c:10:38: error: passing argument 4 of ‘qsort’ from incompatible pointer type [-Wincompatible-pointer-types]
   10 |     qsort(notas, 5, sizeof notas[0], crescente);
      |                                      ^~~~~~~~~
      |                                      |
      |                                      int (*)(const int *, const int *)
In file included from assinatura.c:2:
/usr/include/stdlib.h:999:34: note: expected ‘__compar_fn_t’ {aka ‘int (*)(const void *, const void *)’} but argument is of type ‘int (*)(const int *, const int *)’
  999 |                    __compar_fn_t __compar) __nonnull ((1, 4));
      |                    ~~~~~~~~~~~~~~^~~~~~~~
assinatura.c:4:5: note: ‘crescente’ declared here
    4 | int crescente(const int *a, const int *b) {
      |     ^~~~~~~~~
/usr/include/stdlib.h:970:15: note: ‘__compar_fn_t’ declared here
  970 | typedef int (*__compar_fn_t) (const void *, const void *);
      |               ^~~~~~~~~~~~~

int por_nome(const void *a, const void *b) {
    return strcmp(a, b);
}
…
    const char *turma[] = {"Rui", "Ana", "Lia", "Bruno", "Davi", "Ana Clara"};

$ gcc -std=c23 -Wall -Wextra nomes_errado.c -o nomes_errado
$ ./nomes_errado
Rui
Ana
Lia
Bruno
Davi
Ana Clara

#include <stdio.h>
#include <stdlib.h>

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

int main(void) {
    int saldos[] = {2000000000, -7, -2000000000, 500, 1500000000, -1500000000};
    size_t n = sizeof saldos / sizeof saldos[0];

    qsort(saldos, n, sizeof saldos[0], crescente);

    for (size_t i = 0; i < n; i++) {
        printf("%d\n", saldos[i]);
    }
    return 0;
}

$ gcc -std=c23 -Wall -Wextra subtracao.c -o subtracao
$ ./subtracao
500
1500000000
2000000000
-2000000000
-1500000000
-7
$ gcc -std=c23 -Wall -Wextra -fsanitize=undefined subtracao.c -o subtracao
$ ./subtracao 2>&1 | head -3
subtracao.c:5:28: runtime error: signed integer overflow: 2000000000 - -2000000000 cannot be represented in type 'int'
500
1500000000

    double precos[] = {25.90, 0.75, 18.90, 3.50, 5.99};
    size_t n = sizeof precos / sizeof precos[0];

    qsort(precos, n, sizeof(int), crescente);

$ gcc -std=c23 -Wall -Wextra tamanho.c -o tamanho
$ ./tamanho
0.75 25.90 18.90 3.50 5.99

Referência rápida

Exercícios

Missão final: a vitrine da lojinha

bala   R$  0,75
pao    R$  0,75
agua   R$  4,50
sabao  R$  4,50
sal    R$  4,50
leite  R$  5,99
cafe   R$ 18,90
arroz  R$ 25,90

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct {
    char nome[20];
    int preco;
} Produto;

int comparar(const void *a, const void *b) {
    const Produto *x = a;
    const Produto *y = b;
    // COMPLETE: 1. preços diferentes: o mais barato vem antes
    //           2. mesmo preço: ordem alfabética do nome (strcmp)
    (void)x;
    (void)y;
    return 0;
}

int main(void) {
    Produto loja[] = {
        {"sabao", 450}, {"arroz", 2590}, {"pao", 75}, {"sal", 450},
        {"leite", 599}, {"bala", 75}, {"cafe", 1890}, {"agua", 450},
    };
    size_t n = sizeof loja / sizeof loja[0];

    qsort(loja, n, sizeof loja[0], comparar);

    for (size_t i = 0; i < n; i++) {
        printf("%-6s R$ %2d,%02d\n", loja[i].nome, loja[i].preco / 100, loja[i].preco % 100);
    }
    return 0;
}

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct {
    char nome[20];
    int preco;
} Produto;

int comparar(const void *a, const void *b) {
    const Produto *x = a;
    const Produto *y = b;
    if (x->preco != y->preco) {
        return (x->preco > y->preco) - (x->preco < y->preco);
    }
    return strcmp(x->nome, y->nome);
}

int main(void) {
    Produto loja[] = {
        {"sabao", 450}, {"arroz", 2590}, {"pao", 75}, {"sal", 450},
        {"leite", 599}, {"bala", 75}, {"cafe", 1890}, {"agua", 450},
    };
    size_t n = sizeof loja / sizeof loja[0];

    qsort(loja, n, sizeof loja[0], comparar);

    for (size_t i = 0; i < n; i++) {
        printf("%-6s R$ %2d,%02d\n", loja[i].nome, loja[i].preco / 100, loja[i].preco % 100);
    }
    return 0;
}

Quer ir além? Escreva também uma por_nome e deixe o usuário escolher a ordem com um ponteiro int (*criterio)(const void *, const void *), como na calculadora da aula Ponteiros para Funções. Com a lista ordenada por nome, a próxima aula, Busca (bsearch), acha qualquer produto em poucos passos.

Resumo

• Ordenar é comparar e mudar de lugar. A inserção encaixa cada item entre os já ordenados; é simples, mas lenta com muitos itens.
• qsort(v, n, sizeof v[0], comparar) ordena um array de qualquer tipo: o endereço, quantos itens, o tamanho de cada um e a sua função de comparação.
• A comparação recebe dois const void *, converte para o tipo certo e devolve negativo (a antes), zero (tanto faz) ou positivo (a depois). Use (x > y) - (x < y); x - y pode estourar. Para inverter, troque x e y.
• Textos: strcmp. Num const char *v[], a é um ponteiro para ponteiro (*(const char *const *)a); num char v[][N], a já é o texto.
• Structs: compare o campo que decide e desempate por outro. O qsort não é estável: sem desempate, empatados podem sair em ordens diferentes em cada biblioteca.