Pontifícia Universidade Católica de Goiás

       [pic 1]

                       Pontifícia Universidade Católica de Goiás

                                Engenharia da Computação

                      Aluno: Yann Santana Maciel de Lima

                    

Analise do uso dos algoritmos Bubble Sort e Selection Sort

 Metodologia de pesquisa para ciência da computação

                                        

Goiânia

                                                 2018

Aluno: Yann Santana Maciel de Lima

Analise do uso dos algoritmos bubble sort e selection sort

Projeto apresentado ao curso de Engenharia da computação como parte dos requisitos necessários a obtenção do título de aprovação na matéria de Metodologia de pesquisa para ciência da computação.

Orientador: Solange da Silva

Goiânia

                                                 2018

1. Introdução:

        Os algoritmos de bubble sort e selection sort são algoritmos de ordenação de vetores.

        Devido ao acumulo de dados nos programas, os mesmos estão ficando cada vez mais complicados de se organizar, logo isso está se tonando um problema que precisa ser resolvido.

        Diante deste contexto, este plano de trabalho visa responder a seguinte questão: - Quais as principais semelhanças e diferenças entre os algoritmos Bubble Sort e Selection Sort e quando é interessante usar um dos mesmos?

        Existe trabalhos parecidos na literatura – (GATTO,2017), (HONORATO,2013), (AHKTER,2015) Gatto (2017) descreve somente sobre o algoritmo de Bubble Sort, Honorato (2013) descreve sobre além dos dois algoritmos em questão, fala também sobre o Merge Sort e Quick Sort, mas mostrar seus algoritmos e por último Ahkter (2015) também descreve sobre os mesmos algoritmos que Honorato (2013) porem com mais profundidade. Este utiliza gráficos sobre o tempo de execução no melhor, médio e pior caso.

Neste trabalho analisaremos por meio de pesquisas experimentais, os algoritmos Bubble Sort e Selection Sort. Veremos em quais situações um tem o tempo de execução menor que o outro, quais suas complexidades, o melhor e o pior caso de cada um e as diferenças entre eles

        De acordo com Gatto (2017), o algoritmo Bubble Sort pode ser aplicado para ordenar Arrays e Listas dinâmicas. Seu objetivo é ordenar seus valores de forma decrescente, a posição atual é comparada com a próxima, se for maior eles trocam de posição, se não, eles não fazem nada e passam para o próximo par que será comparado.

        Também de acordo com ela, na linguagem C, e utilizando o comando FOR ela passa por todos os elementos e também podem armazenar seus valores e utilizando o comando IF ela compara o valor da posição atual com o valor da próxima posição.

        Gatto (2017) comenta que o FLAG é utilizado para que não haja repetição desnecessária avisando quando o vetor estiver ordenado, terminando sua execução. O FLAG setará com 1 quando houver troca. Assim, enquanto n (número de valores no vetor) for menor ou igual ao tamanho do vetor e o FLAG for igual a 1, então deve continuar ordenando, caso contrário o vetor estará ordenado.

        No Wikipédia (2018) define que o Selection Sort é um algoritmo que procura sempre passar para a primeira posição o menor valor, após isso mandar o segundo menor para a segunda posição, fazendo isso com seus n-1 elementos que restam até os dois últimos elementos.

        Wikipédia (2018) comenta as vantagens e desvantagens do Selection Sort. De acordo com ele, o algoritmo é simples de ser implementado, não precisa de vetor auxiliar, já que não é usado vetor auxiliar ele ocupa menos memória e ele é uns dos mais velozes na ordenação de vetores pequenos. Em contrapartida ele é bem lento em vetores grandes, não é estável e ele faz n² comparações, mesmo que o vetor já esteja ordenado ou não.

        Honorato (2013) define que o Selection sort sempre passa o menor valor para a primeira posição (ou o maior valor dependendo do que se precisa), o segundo menor para a segunda posição e assim vai até os últimos dois elementos.

Ele comenta que é escolhido um numero a partir do primeiro e esse número é comparado com os números a sua direita, quando ele encontra um número menor, o número escolhido troca de posição com o número menor. Agora esse número encontrado será o novo número escolhido, se não for encontrado nenhum número menor que o escolhido, ele é colocado na posição do primeiro número escolhido e o próximo número a direita será o próximo escolhido para fazer comparações. Esse processo será repetido até o vetor estiver ordenado.

Honorato (2013) comenta que o algoritmo Bubble sort é o algoritmo mais simples e menos eficiente. Nele cada elemento de uma posição será comparado ao elemento i+1, se for maior eles irão trocar de posição. Por conta disso, o vetor será percorrido quantas vezes for preciso, por isso ele diz ser o menos eficiente para listas grandes.

Jairo (2018) cita as vantagens e desvantagens de usar Bubble Sort. Ele afirma que esse algoritmo é um algoritmo simples e estável, em contrapartida ele é lento. Ele indica que esse algoritmo poderá ter um bom rendimento em tabelas muito pequenas e quando já se sabe que a tabela está quase ordenada. Por último ele fala que sua complexidade é de O (n²).

Shi (2015) observa que o Bubble Sort no pior caso e no caso médio tem complexidade de O (n²).

Jonathan (2016) descreve que o Bubble Sort é o tipo mais antigo e simples de algoritmos de ordenação. Ele cita que como vantagem, esse algoritmo é de fácil implementação e estável, em contrapartida mesmo que o vetor já esteja totalmente ordenado a complexidade continuara quadrática.

Daniel (2016) comenta que Selection Sort tem complexidade para todos os casos igual a O (n²) e que não é um algoritmo estável. Ele conclui então que Selection Sort tem complexidade de O (n²) para comparações e O (n) para movimentações, já o Bubble Sort tem complexidade de O (n²) para comparações e para movimentações, ambos têm O (1) para espaço e somente o Selection Sort não é estável dos dois algoritmos.