Objetivo APS 2020-02

Prévia do material em texto

Objetivo 
 O objetivo é desenvolver três tipos de algoritmos em Linguagem Java cujo a 
função é organizar dados de acordo com o tipo/tamanho/quantidade dos dados. 
 Um deles é chamado de Bubble Sort (Cuja tradução ao pé da letra é: Tipo de 
Bolha). O algoritmo é de complexidade quadrática, em prol de mover e/ou manipular 
dados de forma que à complete de acordo com o solicitado. Organiza dados como que 
fossem ‘bolhas’ (Nome atribuído pelo motivo de ‘flutuar’ um valor) de acordo com o seu 
tamanho, percorrendo um vetor quantas vezes necessário indo de uma ponta a outra e 
selecionando os dados com maior valor e levando sempre á ponta até que os valores 
estejam de certa forma organizados. 
 Seguindo a lógica o Shuttler Sort é um algoritmo simples, mas não muito eficiente, 
para organizar um conjunto de n números em ordem de magnitude. O método começa 
com o par de números do lado esquerdo, trocando-os se necessário. O segundo e o terceiro 
números são agora considerados. Se eles forem trocados, o primeiro par será 
reconsiderado. Em seguida, o terceiro e o quarto números são considerados. Se trocados, 
os pares anteriores são novamente reconsiderados, trabalhando da direita para a esquerda. 
Tal como acontece com a classificação por bolha (Bubble Sort algoritmo citado acima), 
podem ser necessárias comparações ½ n (n -1). 
 Um método de classificação baseado em trocas de pares de números. No exemplo, 
× indica uma troca e ‘Ο’ que nenhuma troca é necessária. A classificação funciona da 
esquerda para a direita, reconsiderando os pares anteriores quando uma troca é feita. 
 Cocktail shaker sort (Popularmente conhecido apenas como Shaker Sort cuja 
tradução ao pé da letra é: Tipo Agitador) possui uma ordenação por comparação. O 
algoritmo difere de um bubble sort (Primeiro algoritmo citado no topo desta pagina) no 
qual ordena em ambas as direções a cada iteração sobre a lista. Esse algoritmo de 
ordenação é levemente mais difícil de implementar que o bubble sort, e resolve o 
problema com os chamados coelhos e tartarugas (Tartarugas = pequenos valores; 
Coelhos = grandes valores). Ele possui performance levemente superior ao bubble sort, 
mas não melhora a performance assintótica; assim como o bubble sort, não é muito usado 
na prática.