Please enable JavaScript.
Coggle requires JavaScript to display documents.
Cap 3 - Levitin / Cap 7 Shaffer - Coggle Diagram
Cap 3 - Levitin / Cap 7 Shaffer
Cap 3.1: Selection Sort e Bubble Sort
Selection Sort:
Ele vai sempre caçando o último elemento para coloca-lo na última posição da lista.
Bubble Sort:
Caso os elementos estejam fora de ordem, ele vai trocando até que o maior elemento seja o último da lista.
Cap 4: Diminuir e Conquistar
1- Diminuir por uma constante/ 2- Diminuir por um fator constante/ 3- Diminuição de tamanho variável
Cap 5: Dividir e Conquistar
Os problemas são divididos em subproblemas independentes com tamanhos aproximadamente iguais, que muitas vezes, são resolvidos de forma recursiva. A solução para tais subproblemas, são combinadas para resolver o problema original.
Nem sempre um algoritmo desse tipo será mais eficiente que um de força bruta.
Essa técnica é ideal para cálculos paralelos.
Cap 7: Ordenação Interna
Cap 7.1: Classificação de terminologia e notação
A entrada para os algoritmos de classificação apresentados é uma coleção de registros armazenados em uma matriz.
Os registros são comparados entre si por meio de uma classe comparadora.
Cada registro possui um campo-chave cujo valor é extraído do registro pelo comparador.
7.2.2: Bubble Sort
Consiste em um loop "for" duplo.
Na primeira interação do loop for interno, ele sai comparando e caso um valor de índice inferior for maior que o superior, os valores são trocados.
O tempo de execução do Bubble Sort é praticamente o mesmo no melhor, no médio e no pior dos casos.
O número real de trocas realizadas por Bubble Sort será idêntico ao realizado por Insertion Sort.
7.2.3: Selection Sort
Primeiro encontra a menor chave em uma lista não classificada, depois a segunda menor e assim por diante.
Uma característica única é que há poucas trocas de registros.
O número total de trocas necessárias será n - 1.
7.3: Shellsort
Faz comparações e trocas entre
elementos não adjacentes.
A estratégia de Shellsort é tornar a lista "na maior parte ordenada" de modo que no final o Insertion Sort possa terminar o trabalho.
Divide a lista em sublistas, classificando e recombinando. Por exemplo, se houver 16 elementos, haverá 8 sublistas com 2 elementos cada.
Cada uma dessas listas de 2 elementos é classificada usando Insertion Sort.
7.4: Megasort
A ideia por trás é dividir a lista ao meio, classifique as metades e, em seguida, mescle as metades classificadas.
É um dos algoritmos de classificação mais simples
Mergesort é o método de escolha quando a entrada está na forma de um lista vinculada.