Algoritmos IV

Resolvi resumir nosso estudo sobre algoritmos de ordenação, concluindo esta parte da Série Algoritmos sem explicar o Merge Sort, o Quick Sort e o Bubble Sort (três que eu estava pensando em explicar), mas apenas propondo que algoritmo de ordenação devemos usar para cada caso.

Não vou escrever o custo dos algoritmos de ordenação aqui porque seria uma perda inútil e esse material já pode ser encontrado em vários lugares (na Wikipedia, por exemplo).

Bom... Existem algoritmos de ordenação de vetores bem complexos. Você poderia aprender uma coisa super rápida, mas não vale a pena. Depois de resolver vários problemas que resolvem a ordenação, um professor na UNICAMP (não lembro quem foi) disse:

Não perca tempo com algoritmos de ordenação. Se você programa em C, use qsort; se programa em Pascal ou outra linguagem que não tenha Quicksort implementado, implementa rápido um Insertion Sort.

... e acho que ele estava certo. Talvez para usar em um grande projeto isso não seja o mais indicado, mas para competições não há como fazer melhor. No meio de um algoritmo complexo de fluxo de grafos, por exemplo, eu não tenho tempo para implementar um Quick Sort ou um outro algoritmo de ordenação complexo. Não devemos nos preocupar com isso... Então, usemos algoritmos que tenham implementação fácil, como o Insertion Sort e o Selection Sort. Já que o Insertion Sort tem um custo melhor ( no melhor caso), utilizemos ele.

Isso já discutimos na introdução sobre Ordenação: Basicamente, servem para estudar. O problema de ordenação é um programa muito interessante... Mas aliás, foi pra não desanimar vocês dizendo que não tem muita utilidade prática que resolvi cortar os algoritmos de ordenação por aqui...

QSORT(3) Linux Programmer's Manual QSORT(3)

NAME

qsort - sorts an array

SYNOPSIS

#include <stdlib.h>

void qsort(void *base, size_t nmemb, size_t size,

int(*compar)(const void *, const void *));

Com certeza não é uma das funções mais fáceis de usar... Hehehe... Aliás, confesso que tive alguma dificuldade antes de entender o que isso quer dizer.

Mas é o seguinte... Por o C ser super flexível, você pode criar uma função para comparar dois números. O Qsort exige isto no seu terceiro parâmetro e eu posso fazer o tipo de comparação que eu quiser: ver qual o maior, ver qual o menor ou ver qual tem o fator mínimo maior. Hehehe... É super interessante, mas geralmente não é tão útil, como nesse caso em que só queremos ordenar o vetor de menor pra maior. Então vamos fazer uma função que simplesmente compare dois e diga qual o maior.

O Qsort interpretará o retorno da nossa função da seguinte maneira:

• Se quisermos colocar o primeiro argumento da nossa função antes do segundo em nosso vetor resultante, devemos retornar um número menor que zero.
• Se quisermos colocar o segundo argumento da nossa função antes do primeiro em nosso vetor resultante, devemos retornar um número maior que zero.
• Se retornarmos 0, ele vai colocar em qualquer ordem.

Portanto,

int compara(int *x, int *y) {

if (*x > *y) {

return 1;

}

if (*y > *x) {

return -1;

}

return 0;

}

Bom... Já que não precisamos retornar só 1 e -1, mas sim números maiores que 0 ou menores que 0, poderíamos fazer assim:

int compara(int *x, int *y) {

return *x-*y;

}

Não é verdade?

Não. Essa seria a função mais simples, mas poderia nos causar problemas. Vamos supôr que tentássemos ordenar o e o , que são os números que o seu compilador chama de maior e menor inteiro, respectivamente. Aí ele subtrairia do primeiro o segundo e ia chegar a que número? Ninguém sabe. O programa iria buggar, ele poderia retornar qualquer coisa. Hehehe... Por isso, sempre usemos a de cima e não essa que eu acabei de fazer com a subtração!

E se quiséssemos ordenar de maior pra menor?