Blog de Helton Duarte

Olá pessoal!

Mais uma aula de preparação para a OBI 2009 (principalmente)! Pessoal do IF-RN, preparem-se pesado, porque esse ano precisamos ter alguma medalha! =) A aula de hoje abordará um assunto também bem importante para competidores, visto que otimizar o método de ordenação é um fato muito importante nesse caso (não podemos sempre utilizar o Bubble Sort!).

Aula 4 – Ordenação

Conteúdo: principais aplicações dos algoritmos de ordenação, assim como uma abordagem dos melhores métodos para esse tipo de atividade.

Ordenação é um dos pontos primordias na ciências da computação, estando presente na solução de diversos problemas existentes nas competições e na vida do programador. Muitos algoritmos de ordenação já foram desenvolvidos, sendo necessário saber para que tipo de situação serve cada um (embora já existam muitos os quais não serão mais usados, por haver outros mais otimizados). Nessa aula, procurarei abordar as aplicações mais importantes da ordenação, além de uma teoria a respeito dos principais algoritmos da área.

Aplicações da ordenação:

• Teste de unicidade: Como testar se os elementos de uma coleção S são todos distintos? Ordene-a crencente ou decrescentemente e faça uma varredura testando se S[i] = S[i+1].
• Priorizando eventos: Suponha que existem diversos trabalhos a serem feitos, cada um com seu deadline (data limite). Ordenando-os de acordo com o deadline os  colocará na ordem certa para serem cumpridos.
• Mediana: Se for necessário encontrar o k-ésimo maior item em uma lista S, é preciso apenas ordená-la, tendo o elemento S[k] como o requerido.
• Encontrando o par correto: Como podemos testar se existem dois inteiros x, y em S que x+y = z, onde z é um inteiro qualquer? Ao invés de testar todos os pares possíveis, ordene os números crescentemente. Como S[i] aumenta com o i, o provável parceiro j que tem S[j] = z – S[i] diminui. Com esse método fica bem mais eficiente sua procura.
• Busca eficiente: Para saber se um elemento s encontra-se em S, simplesmente ordena-se e lista e realiza-se uma busca binária na fila, um dos métodos mais comuns de aplicação da ordenação.

Algoritmos de ordenação:

Você já deve ter ouvido muitos algoritmos diferentes para ordenação de dados, no entanto deve estar pensando: para que uma pessoa precisa saber de tantos modos para se fazer a mesma coisa? O real motivo para se estudar todos esses códigos são as ideias por trás dos mesmos, ou seja, o modo como foi desenvolvido certo algoritmo pode ser utilizado para algum problema de uma forma parecida, deu pra entender? Abaixo serão mostrados os três mais interessantes para o estudo da sua teoria:

• Selection Sort – Esse algoritmo divide o vetor de entrada em partes ordenadas e não-ordenadas e a cada varredura pela parte não-ordenada ele encontra o menor elemento e o transfere para o fim da região ordenada. São feitas muitas comparações, todavia é muito eficiente se contarmos o número de troca de posições, pois são apenas n-1, no pior dos casos. Segue no link os códigos em diversas linguagens: Selection Sort.
• Insertion Sort – Esse algoritmo também mantém regiões ordenadas e não-ordenadas. Em cada vez o próximo elemento não-ordenado é movido para a sua posição apropriada na região ordenada. Insertion sort é particularmente eficiente no que diz respeito a quantidade de movimento de dados, pois ele só inverte  um par de elementos para o local já certo, ou seja, em uma lista praticamente ordenada ele pode ser extremamente eficaz. Novamente os códigos seguem com o link: Insertion Sort.
• Quick Sort – É um dos mais eficientes e rápidos, reduzindo o trabalho de ordenar uma grande lista em ordenar duas listas menores. A partição separa o vetor nos elementos menores do que um certo x e os maiores do que o mesmo x. Como nenhum elemento precisará mover-se para fora de sua região, cada vetor menor poderá ser ordenado independentemente. Para facilitar a ordenação o quicksort também recebe como argumentos os índices do começo e fim do sub-vetor. Esse código é muito interessante por diversas razões, pois quando é implementado corretamente consome menos memória do que qualquer outro, além de ser uma das melhores demonstrações do poder da recursividade (uma função que chama ela mesma). Os exemplos em cada linguagem seguem no link: Quick Sort.

Estamos no final da aula, mas não podemos deixar de praticar, não é verdade? Abaixo seguem os exercícios para o treinamento de ordenação:

• Vito’s family – Nível 1
• Stacks of Flapjacks – Nível 2
• Bridge – Nível 3
• Longest Nap – Nível 1
• Shoemaker’s Problem – Nível 2
• CDVII – Nível 2
• ShellSort – Nível 2
• Football (aka Soccer) – Nível 1

PS: Lembrando a todos que o conteúdo desse post e de todo o curso “Programando melhor” é baseado no livro Programming Challenges, de autoria de Miguel Revilla e Steve Skiena e foi permitido o “resumo” e tradução do mesmo pelos próprios autores para a criação desse curso. Além disso os exercícios estão todos disponibilizados no site UVa Online Judge.

Posts interessantes:

• OBI vem aí!
• Programando melhor: Aula 3 – Strings
• Programando melhor: Aula 2 – Estruturas de Dados
• Programando melhor: Aula 1 – Começando
• Cursos grátis na Internet – MIT

Pessoal, mais uma aula completa e dedicação é necessária! Façam sempre os exercícios! Procurarei nas próximas duas semanas, dedicar-me aos exercícios que já foram propostos aqui, colocando dicas para cada um, ok? Além disso, os próprios problemas da seção pratique do site da OBI. Comentem e tirem suas dúvidas! Vamos lá!

Helton de Melo Duarte

“Bem-aventurado o varão que não anda segundo o conselho dos ímpios, nem se detém no caminho dos pecadores, nem se assenta na roda dos escarnecedores.” Salmos 1.1

This entry was posted on quarta-feira, março 11th, 2009 at 12:25 and is filed under Programando Melhor. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.