Algoritmos Computacionais

Artigos sobre lógica de programação por Tiago Madeira

algoritmo: do Lat. algorithmos < Ár. alkharizmi: [Inform.] conjunto de etapas bem definidas necessárias para chegar à resolução de um problema.

Conclusão sobre Ordenação

January 16, 2006

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 ( $LaTeX: \Theta{}(n)$ no melhor caso), utilizemos ele.

Então pra que servem os outros?

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

E como se usa o qsort() no C?

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 $LaTeX: 2^{x}$ e o $LaTeX: -2^{x}$ , 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?

int compara(int *x, int *y) {
	if (*x < *y) {
		return 1;
	}
	if (*y > *x) {
		return -1;
	}
	return 0;
}

Sentiram a flexibilidade da minha linguagem?

Bom... Agora vamos entender os outros argumentos do qsort() (esses são fáceis).

O primeiro argumento é o tão esperado vetor (na verdade, um ponteiro pra ele ;)). O segundo é o número de elementos no vetor. O terceiro é o tamanho que um elemento ocupa na memória.

#include <stdio.h>
#include <stdlib.h>
 
int compara(int *x, int *y) {
	if (*x > *y) {
		return 1;
	}
	if (*y > *x) {
		return -1;
	}
	return 0;
}
 
int main() {
	int i, vetor[]={53, 22, 55, 34, 1, 126, 72};
	qsort(vetor, 7, sizeof(int), (void *)compara);
	for (i=0; i<7; i++) {
		printf("%d ", vetor[i]);
	}
	printf("n");
	return 0;
}

Ah... Esse cast só serve para o GCC não mostrar um Warning (e passarmos o tipo correto pro QSort), mas acho que não faz diferença nenhuma, quer dizer, ele roda sem problemas sem ele.

E como se implementa um Insertion Sort em Pascal?

Isso já fizemos aqui.

E se eu não concordar com nada disso?

Então comente!

Espero que tenham gostado da conclusão sobre algoritmos de ordenação. Queria reforçar que estou fazendo estes artigos baseando-me principalmente em olimpíadas e por isso sempre estou enfatizando problemas como o tempo de implementação e de execução. Para outras situações, temos vários caminhos diferentes para tomar.

Compare Preços de: notebooks, acer aspire, hp pavilion, computadores, pentium 4, nintendo wii, ps3, celulares, câmeras digitais

Categoria(s): Ordenação

6 comentários

#1 | Daniel Quadros (20/01/2006)

Na verdade existem muitos fatores a considerar na hora de escolher um algorítmo de ordenação, particularmente a quantidade de dados a ordenar.

Algorítmos como o Quicksort e Heapsort são um pouco mais complicados que o Insertion Sort, mas podem ter uma vantagem imensa quando a quantidade de dados é grande. O tempo médio do quicksort e do heapsort é proporcional a n*log(n) e do Insertion sort a n*n.

A limitação do Quicksort é que ele é muito lento (cai para n*n) no seu pior caso (que num implementação simplista ocorre quando a entrada já está ordenada!).

Eu gosto muito do Heapsort pelo fato de ser razoavelmente rápido e do tempo variar pouco com os dados sendo ordenados (o tempo máximo é proporcional a n*log(n)). Se, por exemplo, você sabe que no máximo serão ordenados 10.000 registros, basta fazer um teste com um arquivo qualquer com 10.000 registros, se o tempo for bom vai ser bom com qualquer arquivo.

#2 | Tiago Madeira (20/01/2006)

Oi Daniel!

Concordo com você que a quantidade de dados é um dado importante a se analisar. Porém, o principal foco desse artigo foi o uso de um algoritmo de ordenação em uma competição de programação, como a Olimpíada Brasileira de Informática ou a Maratona de Programação…

Não tenho dúvidas de que implementar um Heap Sort seja mais rápido para uma entrada de tamanho razoável (O(n log n) ganha fácil de O(n^2)). Porém, eu acho que numa prova onde temos quatro horas para resolver 4-6 problemas, é bem mais fácil simplesmente rodar um qsort() no C ou implementar um Insertion Sort em Pascal e deixar pra perder tempo com lógicas mais complicadas. Você, que já conhece bem o Heap Sort, conseguiria implementar ele em menos de cinco minutos? Talvez você até consiga, mas sei lá… Pra mim, pelo menos, seria difícil implementar tão rápido. E acho que pra maioria das pessoas que faz essas olimpíadas também. Por isso fiquei por aqui mesmo nos algoritmos de ordenação. Acho que usar um “qsort()” ali na hora é bem mais fácil.

Ah… Só pra complementar, queria deixar claro que não deixei de explicar o Heap Sort por não achá-lo importante, mas porque eu acho que as pessoas teriam dificuldade para compreendê-lo. Desde o início, eu não planejava incluí-lo na série… Heheh… Ainda mais depois que eu fiz um artigo sobre Análise de Algoritmos e já teve muita gente que se perdeu (e olha que eu omiti várias coisas), imagine então ensinando árvores binárias? A própria estrutura heap é meio complicada pra quem não tá acostumado.

Valeu pelo comentário e mande mais sugestões!

#3 | Daniel Quadros (23/01/2006)

Tiago,

Xiii, eu não percebi que você estava falando no contexto de competições (e olha que cheguei no seu site dando um Google de OBI2005!).

Realmente, num contexto destes (e na maioria dos casos) é sempre preferível aproveitar as bibliotecas que vem com a linguagem.

#4 | Tiago Madeira » Conclusão sobre Ordenação (10/12/2006)

[…] O artigo está em outro local agora: Conclusão sobre ordenação […]

#5 | ddd (19/10/2007)

Sauuy

#6 | Antonio carlos pacheco de lima (20/10/2007)

gostei muito do seu artigo estou usando para um trabalho no curso de sistemas de informacao

Escreva um comentário

53 assinantes

Mais artigos

Comentários recentes

Jordana: Eu estou fazendo faculdade de ciencia da computação, na máteria de algoritmo eu estou...
wagnermoral: ola pessoal, to iniciadno no curso Tecnologia de Informação, e to com um...
Estefânia Paula: Adorei a introdução q vc fez sobre algoritmo… Gostaria de saber se tem...
Arnaldo: Estou no primeiro periodo de Sistemas de Informação. Estou com dúvidas em como...
milena de brito sampaio alencar barros: oi tiago! nossa cara valeu mesmo pela explicação do que...
Cleidson Lima da Silva: Bom gostei muito do artigo, explicou de uma maneira mais fácil de ser...
svjwbrxyz bnqtiruv: hsxcwrv mnxlhw pfgwc nedqmyo cskfqt vtzihdf ybdtaumqp
plvr ybncof: pksgtlvwd rauskizvj ebky shjmgoqy nyxlqvbwm sjuexr wote
marconi: caros colegas estou com uma grande dificuldade,preciso de um exemplo de algoritmo q...
Tatiane Hendler: Não é possível não, todos os elementos que aparecerem no teu algoritmo deve,...

Categorias

Escrevo também...

Tiago Madeira
Site pessoal e blog do autor destes artigos
Mal Vicioso
Blog sobre filosofia e sobre a hipocrisia da sociedade

Sobre o design

Este design foi copiado do CSS Zen Garden e modificado com autorização de seu autor, Gunta Klavina.

Licença

Todo o conteúdo deste site (incluindo textos, imagens, arquivos de áudio e quaisquer outros trabalhos), exceto quando especificado o contrário, está licenciado por Tiago Madeira sob uma Licença Creative Commons.

HTML 4.01 gerado por WordPress em 0.895 segundos.