Projeto 2015.1

Equipes formadas. Podem conferir no final da página!

Bubble sort.

O bubble sort (método da bolha) é um dos algoritmos de ordenação dos mais simples. A ideia é percorrer o vetor e trocar as posições dos elementos vizinhos que não estejam ordenados.

A cada percurso do vetor, várias trocas são feitas. É importante observar que isto garante que pelo menos o último elemento estará posicionado. Desta forma, no percurso seguinte, não é necessário se comparar a penúltima com a última posições. E a cada iteração uma quantidade maior de elementos são posicionados ordenados ao final do vetor. Por este motivo, a quantidade de comparações é cada vez menor.

Além disso, se houver um percurso em que nenhuma troca foi feita, então o vetor estará ordenado.

Uma animação que ilustra o funcionamento do Bubble Sort (e de outros algoritmos de ordenação) pode ser vista na seção de humor deste site, aqui.

O projeto.

Na rodapé desta página há um arquivo compactado contendo os dois programas a serem baixados (pode acessar aqui). O primeiro, geraDados.c, gera um arquivo numbers.txt com várias linhas contendo vários números inteiros em cada. O segundo, bubbleSort.c, lê as linhas de inteiros do arquivo numbers.txt e as ordena uma a uma, gravando no arquivo sorted.txt.

Este programa implementa o método bubblesort.

O projeto consistirá em implementar parte do método bubblesort usando as estruturas internas do computador, trocando operações em memória por operações em registradores, e fazendo as trocas utilizando-se operações de bits.

O objetivo é reimplementar o método int bubble(int *toSort, int lim) em linguagem de baixo nível.

Este método percorre o vetor, desde sua posição inicial, até a posição a partir da qual ele necessariamente está ordenado, executando as trocas quando necessário, e as contando. Ao final da execução ele revolve o número de trocas que foi efetuada.

Isto pode funcionar mais rápido usando os registradores, e usando as operações de bits para fazer as trocas eventualmente necessárias.

Use o mínimo de operações possível, e acesse a memória o mínimo de vezes possível.

Entregável.

Um relatório descrevendo

• a)    A implementação, com destaque para eventuais modificações feitas no método método int bubble(int *toSort, int lim), descrevendo de que forma ele funciona depois da alteração.

• b)    Uma discussão sobre porque estas modificações tornam o algoritmo mais rápido

• c)    Resultados de experimentos de ordenação usando o algoritmo original e o que foi modificado, com as devidas considerações estatísticas (intervalo de confiança e erro máximo)

• d)    O que poderia fazer este algoritmo funcionar ainda mais rápido.

Equipes

Para este projeto aceitaremos equipes de no mínimo 1 e no máximo 3 pessoas. Os nomes dos componentes de cada equipe devem ser enviados para o e-mail degas at uesc dot br até a meia noite do dia 10/04/2015. Caso algum nome não esteja em alguma equipe até esta data, então ele será colocado em alguma equipe compulsoriamente formada.

Equipes espontâneas

LETICIA DA SILVA BOMFIM

MARCOS VINICIUS MACEDO BORGES

DIEGO PEREIRA DOS SANTOS

JESSE BENEVIDES SANTOS

RAFAEL RIBEIRO OLIVEIRA

DÁRCIO ROCHA DA SILVA

GLEISSON CARILLO DE SOUZA

ITALO RAMOS PINTO DA CONCEIÇÃO

Equipe compulsória

CESAR AUGUSTO NEVES REIS

SAMUEL SANTOS ALVES