Pesquisa e Ordenação de Dados - ELC118

Professora Marcia Pasin


UFSM > Ciência da Computação > Minha página > Pesquisa e Ordenação de Dados > Trabalho T1

Francisco Tiago Avelar (avelar@inf.ufsm.br)
Primeiro semestre de 2006
Carga horária: 60h

Descrição do trabalho T1.

Implementar os métodos de ordenação Seleção e Heapsort nas linguagens de programação Java e Modula-2.

Os dados de entrada deverão estar dispostos na forma crescente, decrescente e desordenada.

Calcular o tempo de execução em cada caso, executando o programa três vezes. Efetuar a média entre os três valores de tempo.


Desenvolvimento em Modula-2.

Os métodos de ordenação Seleção e Heapsort foram desenvolvidos em ambiente Linux (SuSE Linux versão 9.3) e o compilador utilizado foi o XDS.

Para maiores informações sobre o ambiente de desenvolvimento, visite as páginas abaixo:

Compilador XDS.
http://www.excelsior-usa.com/xds.html
Suse Linux
http://www.novell.com/linux/

Para fazer o download completo da implementação em Modula-2 dos métodos de ordenação Seleção e Heapsort, clique para baixar o arquivo abaixo.

Arquivo compactado implementação em Modula-2.
Método Seleção

http://www.inf.ufsm.br/~avelar/elc118/t1/codigos/modula2/selecao.tgz
Método Heapsort
http://www.inf.ufsm.br/~avelar/elc118/t1/codigos/modula2/heapsort.tgz

A compilação dos arquivos de interface pode ser realizada pelo comando, via console

 ./xc < nome_do_arquivo >.def

Uma vez sendo necessário compilar os arquivos de interface, a compilação do código-fonte .mod se resulta pelo seguinte comando

 ./xc =m < arquivo_fonte >.mod

A interface é compilada através do arquivo de definição de interface .def correspondente gerando um arquivo intermediário .sym. A implementação da interface .mod e a sua definição .def devem estar em um mesmo caminho de diretório para garantir que a ligação com o arquivo principal seja efetuada para gerar o programa executável.

Certifique-se de que todos os arquivos estejam na pasta bin/ do compilador XDS. Uma outra forma é apontar um caminho (PATH) para que o compilador XC seja visto em qualquer caminho de diretório.

Para ler a página contendo a documentação do trabalho, clique para visualizar em seu navegador Internet.


Arquivo HTML da implementação do método de ordenação por seleção.
http://www.inf.ufsm.br/~avelar/elc118/t1/codigos/modula2/selecao.html
Arquivo HTML da implementação do método de ordenação por Heapsort.
http://www.inf.ufsm.br/~avelar/elc118/t1/codigos/modula2/heapsort.html


Desenvolvimento em Java.

Os métodos de ordenação Seleção e Heapsort foram desenvolvidos no mesmo ambiente SuSE Linux e o aplicativo utilizado foi o NetBeans 5.0 com a máquina virtual Java versão 1.5.0_06-b05. Para maiores informações sobre as ferramentas de utilização, visite os websites.

Máquina Virtual Java.
http://www.java.com/en/download/index.jsp
NetBeans IDE
http://www.netbeans.org/

Para fazer o download completo da implementação em Java dos métodos de ordenação Seleção e Heapsort, clique para baixar o arquivo abaixo.
Arquivo compactado implementação em Java.
Método Seleção

http://www.inf.ufsm.br/~avelar/elc118/t1/codigos/java/selecao.tgz
Método Heapsort
http://www.inf.ufsm.br/~avelar/elc118/t1/codigos/java/heapsort.tgz

Referente aos métodos de ordenação por seleção e por heapsort, o arquivo principal se chama selecao.java e heapsort.java, respectivamente. Os demais arquivos são compilados automaticamente através de javac.

Após compilado o código em Java, o programa deve ser executado de acordo com a seguinte sintaxe através da chamada de programa via console.

java < <[selecao] [heapsort]> <[-c] [-d] [-a]> <[100] [1000] [10000]> <[-s] [-n]> >

Os campos delimitados pelos símbolos matemáticos de desigualdade correspondem aos campos obrigatórios. Os itens delimitados por colchetes são formas alternadas de compor o mesmo campo, resultando numa saída diferente de programa. A tabela explica a situação.

[selecao] [heapsort]
Método de ordenação a ser escolhido. Seleção ou heapsort.
[-c] [-d] [-a]
Forma de entrada de dados dispostos numa seqüência linear (array unidimensional).
-c : crescente
-d : decrescente
-a : aleatória/desordenada
[100] [1000] [10000]
Quantidade de números que são dispostos em seqüência para serem ordenados. Há a possibilidade de entrar com uma quantia arbitária de números.
[-s] [-n]
Opção de impressão na tela da seqüência ordenada.
-s : sim (o array será mostrado na tela)
-n : não (o array não é exibido)

Por exemplo, se desejar ordenar uma seqüência aleatória de cem valores através do método heapsort e imprimir na tela, execute, no console, o comando:

java heapsort -a 100 -s

Para ler a página contendo a documentação do trabalho, clique para visualizar.
Arquivo HTML da implementação do método de ordenação por seleção.
http://www.inf.ufsm.br/~avelar/elc118/t1/codigos/java/selecao.html
Arquivo HTML da implementação do método de ordenação por Heapsort.
http://www.inf.ufsm.br/~avelar/elc118/t1/codigos/java/heapsort.html


Considerações finais de análise de desempenho.

Seqüência de entrada crescente.

Embora a seqüência já esteja disposta de forma crescente, os algoritmos de ordenação por seleção e por heapsort efetuam a verificação de ordem de cada valor do array, resultando, dessa forma, num trabalho redundante.

O desempenho demonstra ser ligeiramente modificado conforme a quantidade de números no array. Certas contradições podem ocorrer em relação a um desempenho mais eficiente para uma seqüência com quantidade maior de valores. Isso se justifica pelo teste de execução de programa que analisou o tempo de sucessivas execuções de programa com diferentes tamanhos de array. Dessa forma, a memória principal apresenta uma pré-disposição para alocação mais afetiva de uma seqüência de valores para uma simulação subseqüente.


Seqüência de entrada decrescente.

Uma seqüência decrescente de valores representa o pior caso para o método de ordenação por seleção e heapsort em ordem crescente, visto que o número de substituições internas no array é sempre verdadeiro em todos os passos de execução do algoritmo.

A quantidade de valores decrescentes dispostos no array para serem ordenados de forma ascendente é diretamente proporcional ao o tempo utilizado para ordenação.

Nesse caso em que o pior caso é simulado através da execução de programa, as diferenças de tempo de execução são mais evidentes no ponto de vista de desempenho.


Seqüência de entrada desordenada/aleatória.

Uma seqüencia de elementos disposta de forma desordenada para uma ordenação seletiva e heapsort representa um caso intermediário de inserção de dados em relação a um array crescente e um array decrescente.

Certas contradições de tempo são visíveis. A justificativa é dada mais uma vez pela sucessão de alocações e liberações de memória durante a execução de programa com ordenação de diferentes tamanhos de array.

Comparação entre os métodos de ordenação.

O método de ordenação por seleção apresenta uma forma menos eficiente de ordenar uma seqüência de valores, visto que necessita de diversos percursos no array no objetivo de encontrar o menor valor e substituir na posição correta. Contudo, para quantidades pequenas de dados, a ordenação por seleção apresenta resultados favoráveis em termos de desempenho.

O método de ordenação por heapsort apresenta um algoritmo mais complexo e possui maior eficiência em ordenar valores, pois não necessita comparar cada valor num array para posicionar de forma correta. O maior custo que se possui é na criação de uma árvore heap. Uma vez o array disposto nessa forma, o heapsort apresenta grande desempenho. O maior ganho expressivo desse método se obtém através da ordenação de um grande conjunto de dados.



Última atualização em 27 de junho/2006, 16:25.