Resumo

Prévia do material em texto

Atividade Avaliativa – 01 – EDII
1-Título
“Comparação dos Algoritmos Bubble Sort, Insertion Sort, Insertion Sort Bin e Shell Sort”
2- Autores
Davi Borges, Shirley Louzada
3- Introdução
O presente trabalho irá mostrar o tempo em segundos entre os seguintes algoritmos: Bubble Sort, Insertion Sort, Insertion Sort Bin e Shell Sort, iremos concluir classificando qual algoritmo é o mais eficiente e o menos eficiente numa ordenação de poucos registros até registros relativamente grandes. Os tamanhos dos registros que iremos utilizar são: 1.000, 10.000, 100.000, 200.000, 400.000, 800.000.
- Uma breve descrição dos algoritmos:
- Bubble Sort: O bubble sort, ou ordenação por flutuação (literalmente "por bolha"), é um algoritmo de ordenação dos mais simples. A ideia é percorrer o vetor diversas vezes, a cada passagem fazendo flutuar para o topo o maior elemento da sequência. Essa movimentação lembra a forma como as bolhas em um tanque de água procuram seu próprio nível, e disso vem o nome do algoritmo. No melhor caso, o algoritmo executa {\displaystyle n}n operações relevantes, onde n representa o número de elementos do vetor. No pior caso, são feitas {\displaystyle n^{2}}n2 operações. A complexidade desse algoritmo é de ordem quadrática. Por isso, ele não é recomendado para programas que precisem de velocidade e operem com quantidade elevada de dados.
- Insertion Sort: Insertion Sort, ou ordenação por inserção, é o algoritmo de ordenação que, dado uma estrutura (array, lista) constrói uma matriz final com um elemento de cada vez, uma inserção por vez. Assim como algoritmos de ordenação quadrática, é bastante eficiente para problemas com pequenas entradas, sendo o mais eficiente entre os algoritmos desta ordem de classificação. Podemos fazer uma comparação do Insertion Sort com o modo de como algumas pessoas organizam um baralho num jogo de cartas. Imagine que você está jogando cartas. Você está com as cartas na mão e elas estão ordenadas. Você recebe uma nova carta e deve colocá-la na posição correta da sua mão de cartas, de forma que as cartas obedeçam à ordenação.
A cada nova carta adicionada a sua mão de cartas, a nova carta pode ser menor que algumas das cartas que você já tem na mão ou maior, e assim, você começa a comparar a nova carta com todas as cartas na sua mão até encontrar sua posição correta. Você insere a nova carta na posição correta, e, novamente, sua mão é composta de cartas totalmente ordenadas. Então, você recebe outra carta e repete o mesmo procedimento. Então outra carta, e outra, e assim por diante, até você não receber mais cartas.
Esta é a ideia por trás da ordenação por inserção. Percorra as posições do array, começando com o índice 1 (um). Cada nova posição é como a nova carta que você recebeu, e você precisa inseri-la no lugar correto no subarray ordenado à esquerda daquela posição.
Insertion Sort Bin: O algoritmo de Ordenação por Inserção Binária é basicamente a mesma coisa que o de normal a única diferença está em sua característica binária de dividir para conquistar que tende ir ordenado de forma binária. Assim, pode-se utilizar um método mais rápido para determinar o ponto correto de inserção. A escolha óbvia é a busca binária, que divide a sequência destino no seu ponto central, continuando a divisão até encontrar o ponto correto de inserção.
 - Shell sort:  Shell sort é o mais eficiente algoritmo de classificação dentre os de complexidade quadrática. É um refinamento do método de inserção direta. O algoritmo difere do método de inserção direta pelo fato de no lugar de considerar o array a ser ordenado como um único segmento, ele considera vários segmentos sendo aplicado o método de inserção direta em cada um deles. Basicamente o algoritmo passa várias vezes pela lista dividindo o grupo maior em menores. Nos grupos menores é aplicado o método da ordenação por inserção. 
4- Resultados dos Testes
O Bubble Sort, Insertion Sort, Insertion Sort Bin, obteve a mesma eficiência que os outros algoritmos nos registros iniciais de menores valores. O Bublle Sort nos registros maiores não manteve a mesma eficiente comparando com os outros algoritmos. O Shell Sort obteve eficiência do inicio ao fim dos testes dos menores até os maiores registros.
5- Conclusão
De acordo com os testes realizados, concluímos que o Shell Sort é o algoritmo mais eficiente e o Bubble Sort é o algoritmo menos eficiência.
6- Referências 
https://pt.wikipedia.org/
http://marceloaguiar.pro.br/