Baixar este arquivo PDF - Revista Eletrônica Unicruz

Análise e Comparação de Algoritmos Implementados em Java
Jonathan S. Nascimento1, Patricia M. Mozzaquatro1, Rodrigo L. Antoniazzi1
1
Departamento de Ciência da Computação
Universidade de Cruz Alta (UNICRUZ) – Cruz Alta, RS – Brazil
{jonathanjsn, patriciamozzaquatro}@gmail.com, [email protected]
Abstract. This article aims to show comparison tests between sorting algorithms
on lists of increasing, decreasing and random order, analyzing the performance
of each of them. By means of tables is shown the amount of comparisons and
outgoing exchange, and display the execution time of each method. The
algorithms used are the bubblesort, insertionsort, combsort and shellsort, all
implemented in the Java language.
Resumo. Este artigo tem por finalidade demonstrar testes de comparação entre
algoritmos de ordenação sobre listas de ordem crescente, decrescente e
aleatória, analisando a performance sobre cada uma delas. Por meio de tabelas
será demonstrado a quantidade de comparações e trocas efetuadas, além de
exibir o tempo de execução de cada método. Os algoritmos utilizados serão o
bubblesort, insertionsort, combsort e shellsort, todos implementados na
linguagem java.
1. Introdução
A ordenação consiste em arranjar os elementos de um conjunto de modo a facilitar a
posterior recuperação ou análise dos dados. Por ser tão importante a ordenação é uma das
atividades mais utilizadas na computação (BITENCOURT, 2014).
Existem várias maneiras de implementar um algoritmo de ordenação, mas há um
porém quanto a necessidade de uso de cada um. Cada algoritmo resolve um problema
comum que é a ordenação, mas como cada um se comporta de uma maneira diferente
devemos entender como funciona cada um para que saibamos qual usar para resolver
determinado problema. O uso deles nos permite resolver um problema de forma dinâmica,
ou seja, após implementado um algoritmo para ordenar um vetor em ordem crescente por
exemplo, ele deverá ser funcional a qualquer vetor independentemente da quantidade de
valores ou da forma em que esses valores estão dispostos na situação inicial em que se
encontram no vetor.
Para testar se um método é eficaz, utilizaremos dois tipos de avaliações sobre os
resultados finais comparando os algoritmos. A avaliação empírica, no qual é medido o
tempo de execução de cada método, e a avaliação assintótica, que calcula o número de
trocas realizadas para a ordenação, no qual será avaliado o desempenho dele. O resultado
da análise empírica dependerá da linguagem de programação, e da capacidade de
processamento da máquina utilizada, enquanto da assintótica depende mais da lógica de
como foi implementado. Será usado uma lista de elementos inteiros de 1.000, 10.000 e
100.000 posições para cada método que será testado ordenados aleatoriamente. Neste
artigo apresentaremos os algoritmos de ordenação BubbleSort, CombSort, InsertSort e
ShellSort.
2. Métodos de Ordenação
Os métodos de ordenação são classificados em dois grandes grupos: ordenação interna e
externa.
1. Ordenação Interna: São os métodos que não necessitam de uma memória
secundária para o processo, a ordenação é feita na memória principal do computador;
2. Ordenação Externa: Quando o arquivo a ser ordenado não cabe na memória
principal e, por isso, tem de ser armazenado em fita ou disco.
A principal diferença entre os dois grupos é que no método de ordenação interna
qualquer registro pode ser acessado diretamente, enquanto no método externo é
necessário fazer o acesso em blocos (OLIVEIRA, 2002).
Neste artigo falaremos apenas sobre os métodos de ordenação interna.
2.1 Métodos de Ordenação Interna
Durante a escolha de um algoritmo de ordenação, deve-se observar um aspecto importante:
o tempo gasto durante a sua execução. Para algoritmos de ordenação interna, as medidas
de complexidade relevantes contam o número de comparações entre as chaves e o número
de movimentações de itens do arquivo (ZIVIANI, 2007).
Outra medida que pesa na escolha é a quantidade de memória extra utilizada pelo
algoritmo. Métodos que realizam a permutação dos elementos no próprio vetor são
chamados in situ, esses métodos são os preferidos. Os métodos que necessitam de
memória extra para armazenar outra cópia dos itens possuem menor importância
(ZIVIANI, 2007).
2.2. Bubble Sort
O método de ordenação bubble sort usa uma estratégia de “comparação e troca”, que pode
ser aplicada em vários vetores a ser ordenados (OLIVEIRA, 2002).
O Bubble Sort é o tipo mais antigo e mais simples usado para ordenações. Ele
funciona comparando cada item da lista com o item do lado dele, e efetua a troca se o
valor na posição que está sendo analisada for maior que o da posição após a dele. O
algoritmo repete este processo até passar por todas as posições da lista. Isto faz com que
os valores maiores “flutuem” para o final da lista, enquanto os valores menores “afundem”
para o início da lista.
Este método tem o pior caso medido por O(n²), onde n é o número de elementos
do vetor. Mesmo outros métodos como o insertion sort que tem pior caso denominado por
O(n²), tendem a ter melhor desempenho que o método bolha.
Vantagens: é um algoritmo de fácil implementação, algoritmo estável.
Limitações: O fato de o arquivo estar ordenado não ajuda em nada, ordem de complexidade
quadrática (MENNOTI, 2008).
2.3. Comb Sort
A idéia básica é a de eliminar as “tartarugas”, que são valores pequenos perto do final
da lista, uma vez que no método Bubble Sort é isso que causa a lentidão na ordenação.
Enquanto “coelhos” que são grandes valores ao redor do início da lista, não representam
um problema em bubble sort (BREJOVÁ, 2001).
Em Bubble Sort, quando quaisquer dois elementos são comparados, eles sempre
têm um gap (distância um do outro) de 1. A idéia básica do tipo pente é que a diferença
pode ser muito mais do que 1 (Shell espécie também é baseado nesta idéia , mas é uma
modificação do tipo de inserção, em vez de Bubble Sort).
Em outras palavras, o circuito interno de Bubble Sort, que faz a troca real, é
modificado de tal modo que o gap entre elementos trocados vá diminuindo (para cada
iteração do loop externo) em etapa pelo fator de contração. ou seja, [tamanho de entrada
/ fator encolhimento]. Ao contrário de bubble sort, onde a diferença é constante ou seja,
1 (BREJOVÁ, 2001).
O fator de encolhimento, ou gap, tem um grande efeito sobre a eficiência do
método. No artigo original, os autores sugerem 1.3. Um valor muito pequeno retarda a
eficiência do algoritmo porque mais comparações devem ser feitas, enquanto que um
valor demasiado grande impediria que algumas comparações fossem feitas.
Impiricamente falando, (testando Combsort em mais de 200.000 listas aleatórias) o fator
de contração de 1,3 seria o melhor (BREJOVÁ, 2001).
2.4. Insertion Sort
Dentre os métodos de inserção, o método da Inserção Direta é o mais simples, porém, é
o mais rápido, entre os outros métodos considerados básicos – Bubble Sort e Selection
Sort (PASSARO, 2006). Neste algoritmo, o próprio vetor é utilizado no processo de
ordenação, não consumindo, portanto, memória para a separação dos segmentos do vetor,
consome-se um pouco de memória somente para o armazenamento de variáveis auxiliares
(PASSARO, 2006).
Todavia, a eficácia do método de inserção está intrinsecam ente ligada a uma
adequação aos seguintes fatores: o número de registros a serem classificados; se todos os
registros caberão ou não na memória interna disponível; e o grau de classificação já
existente; No entanto, a ordenação por inserção tem duas vantagens. Primeiro, ela se
comporta naturalmente, ou seja, trabalha menos quando a matriz já está ordenada e o
máximo quando a matriz está ordenada no sentido inverso. Isso torna a ordenação por
inserção excelente para listas que estão quase em ordem. A segunda vantagem é que ela
não rearranja elementos de mesma chave. Isso significa que um vetor que é ordenado por
duas chaves permanece ordenado por ambas as chaves após uma ordenação por inserção
(CCET-VIRTUAL, 2006).
Quanto a seu funcionamento, conceitualmente o método da inserção pode ser
entendido como “a classificação de um conjunto de registros que é feita inserindo
registros num sub-arquivo classificado anteriormente, ou seja, a inserção de um elemento
é feita na posição correta dentro de um sub-arquivo classificado [...]” (CEFETPB, 2006),
ou ainda “[...] Os elementos são conceitualmente divididos em uma seqüência destino
A1...A i-1 e uma seqüência fonte Ai...An . Em cada passo, iniciando-se com i=2 e
incrementando-se i de uma em uma unidade, o i-ésimo elemento da seqüência vai sendo
retirado e transferido para a seqüência destino, e inserido na posição apropriada [...]”
(WIRTH, 1999) e [...] “... o vetor C é dividido em dois segmentos. Inicialmente, o
primeiro segmento contém apenas o primeiro elemento, estando, portanto, classificado,
enquanto o segundo segmento contém os elementos C[2], C[3],...C[n], sendo n o número
de elementos do vetor. Por meio de iterações sucessivas cada elemento do segundo
segmento é inserido ordenadamente no primeiro, até que todos os sejam (VELOSO, 1983).
Vantagens: É um algoritmo de fácil implementação, algoritmo estável, o vetor já
ordenado favorece a ordenação.
Limitações: Número grande de movimentações, ordem de complexidade
quadrática, ineficiente quando o vetor está ordenado inversamente (MENNOTI, 2008).
2.5. Shell Sort
Shell Sort, é uma comparação do tipo in-place. Ele pode ser visto tanto como uma
generalização da classificação por troca (Bubble Sort) ou a classificação por inserção
(ordenação por inserção) (KNUTH, 1997).
O método de ordenação Shell Sort contorna o problema método de inserção de
encontrar seu ponto de inserção, permitindo trocas de registros que estão distantes um do
outro. Os itens que estão separados h posições e são rearranjados de tal forma que todo
h-ésimo item leva a uma sequência ordenada. O valor de h pode ser estipulado para uma
determinada implementação, somente não podem ser utilizados valores múltiplos, sob
pena de perda de performance. Tal sequência é dita estar ordenada. Para a sequência de
incrementos utilizada no algoritmo existem duas conjecturas para o número de
comparações: C (n) = O (n1,25) e C(n) = O(n (ln n)2), e isto ainda não foi determinada,
segundo Ziviani (2002, p.77) por ter alguns problemas matemáticos complexos.
O método começa classificando pares de elementos distantes um do outro, em
seguida, reduzindo progressivamente a diferença entre elementos para ser comparados.
Começando com distantes elementos pode mover alguns elementos fora de lugar na
posição mais rápido do que uma simples troca de vizinho mais próximo (SHELL, 1959).
Donald Shell publicou a primeira versão deste tipo em 1959.
Vantagens: O algoritmo tem o código simples, interessante para arquivos de
tamanho moderado.
Limitações: Algoritmo não estável, tempo de execução sensível à ordem inicial
do arquivo (MENNOTI, 2008).
3. Desenvolvimento
O programa foi desenvolvido com a finalidade de realizar uma análise empírica e
assintótica de algoritmos de ordenação. Para que fosse possível obter uma melhor
visualização das comparações dos resultados, foi criada uma interface gráfica conforme
mostra a Figura 1.
Figura 1. Tela de análise dos algoritmos.
Em sua primeira etapa, o usuário deve preencher os itens tamanho e variedade do vetor a
ser gerado, inserindo além disso o tipo da ordenação inicial deste vetor, seja ela crescente,
decrescente ou aleatória. Após ser gerado, será criado um arquivo com a extensão “.txt”
contendo os números na ordem em que foi selecionado, podendo o usuário visualizar
estes números na tela do programa.
A segunda etapa é escolher qual método será utilizado para ordenar este vetor.
Assim que é realizada a escolha do método o programa demonstrando a quantidade de
comparações, trocas e o tempo de execução que o método utilizou para esta ordenação,
demonstrado na Figura 2.
Figura 2. Resultado da análise
4. Resultados
Os métodos foram testados em um computador com processador AMD FX (tm)-8320
Eight-Core 3.50 Ghz, com 4 GB de memória RAM. Foi gerado um vetor de ordem
crescente, decrescente e aleatório para cada uma das listas de 1.000, 10.000, e 100.000
posições, na qual foram testadas com cada método, registrando o número de comparações,
trocas e tempo total de execução.
Para os vetores de ordem crescentes e decrescentes, a lista usada e a variedade de
elementos foram referentes ao tamanho do vetor. Para vetor de tamanho 1.000,
começando pelo elemento 1 (um) até o 1.000 (mil) e assim por diante para as outras listas.
Para o vetor aleatório foi utilizado um método randômico, utilizando a classe
java.util.Random, sendo que essas listas que foram geradas, foram armazenadas para
serem usadas com todos os métodos, para garantir maior precisão nos resultados.
4.1 Vetor de ordem crescente
A Tabela, apresenta o número de comparações e trocas relacionadas a cada método,
utilizando o conceito de análise assintótica. Enquanto a Tabela 2 mostra o tempo total de
execução para a ordenação da lista, analisado empiricamente. O tempo foi mostrado
através do método System.currentTimeMillis() do Java armazenado em uma variável long
convertida para segundos.
Tabela 1. Comparações e trocas, com vetor de ordem crescente.
Tabela 2. Comparação de tempo entre métodos, com vetor de ordem crescente.
Baseado nas tabelas acima, percebe-se que o Insertion Sort foi o que menos fez
comparações, e o Bubble Sort teve o maior índice de comparações. O único a demonstrar
algum tempo significativo neste exemplo de vetor crescente foi o Bubble Sort.
4.2 Vetor de ordem decrescente
A Tabela 3, apresenta o número de comparações e trocas relacionadas a cada método,
utilizando o conceito de análise assintótica. Enquanto a Tabela 4 mostra o tempo total de
execução para a ordenação da lista, analisado empiricamente.
Tabela 3. Comparações e trocas, com vetor de ordem decrescente.
Tabela 4. Comparação de tempo entre métodos, com vetor de ordem decrescente.
Nesta fase de testes, com um vetor decrescente, observou-se que o Shell Sort foi
superior ao Comb Sort com relação a comparações, mas, no entanto, fez mais trocas.
Quanto ao Bubble Sort e Insert Sort, foram os únicos a ser possível demonstrar o tempo
de execução.
4.3 Vetor Aleatório
A Tabela 5, apresenta o número de comparações e trocas relacionadas a cada método,
utilizando o conceito de análise assintótica. Enquanto a Tabela 6 mostra o tempo total de
execução para a ordenação da lista, analisado empiricamente.
Tabela 5. Comparações e trocas, com vetor randômico.
Tabela 6. Comparação de tempo entre métodos, com vetor randômico.
Nesta etapa final, usando um vetor randômico, outros métodos já puderam ser
avaliados com referência ao tempo de execução, devido a lista ter sido gerada com valores
aleatórios em suas posições. Avaliando, percebemos que o Bubble Sort e o Insertion Sort
tiveram menor desempenho. Quanto ao tempo de execução, o Comb Sort saiu-se melhor
em relação aos demais.
5. Conclusão
Foram avaliados quatro métodos de ordenação, no qual deu-se importância a quantidade
de comparações e de trocas que cada um realizou, e o tempo de execução, todos testados
com vetores de 1.000, 10.000 e 100.000 posições de ordem crescente, decrescente e
aleatório.
Conclui-se então:
1. Bubble Sort: Apresentou-se com o pior desempenho dos métodos testados,
um dos motivos é a quantidade de comparações desnecessárias.
2. Insert Sort: O desempenho em relação a outros métodos depende da
ordenação do vetor em sua fase inicial, sendo que demonstrou ser bastante
eficaz em vetores com poucos elementos fora de ordem, e teve o menor
índice de comparações relacionado a estes.
3. Comb Sort: Demonstrou ter bom desempenho quando se trata de vetores
desordenados em ordem decrescente, ou aleatórios, pois teve o menor
índice de trocas em relação a todos os métodos demonstrados.
4. Shell Sort: Em relação ao número de comparações, foi o que melhor
obteve êxito, além de realizar mais trocas que o Comb Sort, manteve o
desempenho comparado ao tempo de execução.
Conclui-se então, que a escolha do algoritmo a ser usado depende da lista que ele
irá ordenar, do tamanho que essa lista tem e do quão desordenados estão os elementos.
Foi notado que o algoritmo Bubble Sort tem um desempenho baixo em relação aos outros,
constatando então que esse possivelmente seria descartado.
Baseado nos testes realizados até então, podemos constatar que os algoritmos
sofisticados têm maior efetividade na ordenação, e seria aconselhável usá-los para
ordenação de listas de tamanho médio e moderadamente grandes. Quanto aos algoritmos
simples, no caso o Insertion Sort, possivelmente seria usado em uma lista de tamanho
pequeno onde os elementos do vetor estão quase totalmente ordenados.
6. Referências
OLIVEIRA, Á. B. . Métodos de Ordenação Interna. Visual Book, São Paulo, 1st edição,
2002.
ZIVIANI, N. . Projeto de Algoritmos com implementação e C++ e Java. THOMPSON
Learning, São Paulo, 1st edição 2007.
MENNOTI, D. . Algoritmos e estrutura de dados – Métodos de ordenação interna, 2008.
<http://webcache.googleusercontent.com/search?q=cache:AwIkQANy6D4J:
www.decom.ufop.br/menotti/aedI082/tps/tp3-sol1.pdf+&cd=2&hl=pt-BR&ct=clnk
&gl=br>. Acessado em 13/05/2015.
PÁSSARO, Â. Projeto e Análise de Algoritmos.Algoritmos de Ordenação.
<http://www2.brazcubas.br/professores1/arquivos/12_angelopassaro>. Acessado em
18/08/2006.
CCET-VIRTUAL. Vetor. <http://ccet.ucs.br/dein/napro/java/>. Acessado em18/08/2006.
CEFETPB. Classificação de Dados-Métodos de Classificação Interna.
<http://arquivos.coinfo.cefetpb.edu.br/~fred/>. Acessado em 18/08/2006.
WIRTH, N. .Algoritmos e estruturas de dados. Tradução de Cheng Mei Lee. Livros
técnicos e científicos, Editora S.A .Rio de Janeiro, 1999, 255p.
VELOSO, P. . Estruturas de Dados. Editora Campus, 15ª Edição, 228 p. 1983.
KNUTH, D. . Shell's method. The Art of Computer Programming. Volume 3: Sorting
and Searching (2nd ed.). Reading, Massachusetts: Addison-Wesley. pp. 83–95, 1997.
SHELL, D.L. . A high-speed sorting procedure. Communications of the ACM 2 (7): 30–
32, 1959.