Please enable JavaScript.
Coggle requires JavaScript to display documents.
Algoritmos de Ordenação - Coggle Diagram
Algoritmos de Ordenação
Força Bruta
Selection Sort
O algoritmo de Selection Sort começa iterando do primeiro ao último item da lista para trocar de lugar o item de menor valor com o primeiro
Depois, ele repete o processo iterando do segundo item ao último
O processo se repete até o penúltimo item da lista. Após isso, ela estará ordenada
A ideia de comparar cada item da lista para procurar os menores valores é muito simples de se conceber, mas a repetição dessa comparação classifica o algoritmo como teta n^2
Esses algoritmos não são concentrados em ser o mais eficientes possível, são repostas rápidas e ideias simples para resolver o problema de como ordenar uma array com n elementos
Bubble Sort
O algoritmo de Bubble Sort difere do de Selection Sort porque, no lugar de comparar um item com os outros na lista, os itens são comparados com seus vizinhos
O algoritmo itera pela array comparando um elemento com o elemento seguinte. Se o seguinte for maior, eles são trocados de lugar. Assim, os elementos de maiores valores são levados ao fim da lista
-
Reduzir e Conquistar
Se trata de algoritmos que aumentam sua eficiência baseando a solução de um problema sob um input de tamanho n em soluções de subproblemas de tamanho menor
Redução por constante
Uma forma de fazer isso é analisar o comportamento do problema para um input de tamanho de tamanho n - a, a sendo um número inteiro
Assim, podemos analisar como funcionaria um algoritmo de tamanho n - a - a - a - a ... - a até que fosse encontrada o caso mais simplificado possível para ser usado de base
-
-
-
Insertion Sort
O algoritmo de Insertion Sort considera que, quando opera em uma array A[0 ... n-1], já tenha sido solucionado o problema para a array A[0 ... n-2]
Assim, para terminar de ordenar a lista, basta iterar pela parte já ordenada para encontrar uma posição adequada para inserir o último elemento
Apesar de sua ideia de natureza recursiva, a versão mais eficiente do algoritmo é sua implementação bototm up (iterativa)
Ela considera o primeiro elemento como uma array já ordenada e age sob os elementos seguintes da forma já descrita
Percebe-se claramente a natureza recursiva do algoritmo, sendo a solução para um input dependente da solução de sua versão reduzida
Apesar de seu pior caso ser apenas tão eficiente quanto os algortimos de ordenação de força bruta, seu caso médio é em torno de duas vezes mais eficiente
Além disso, o algoritmo é muito eficiente para casos de arrays já quase ordenadas, o que o torna preferível aos de força bruta como Selection Sort e Bubble Sort
Dividir e Conquistar
Dividir e conquistar é um dos métodos mais populares para design de algoritmos hoje. Ele se baseia nos seguintes passos:
Um problema é divido em subproblemas de mesmo tipo e, idealmente, mesmo tamanho
-
Nem sempre algoritmos desse tipo geram soluções mais eficientes, mas muitas vezes eles são significativamente mais rápidos
Mergesort
Mergesoft é uma implementação do conceito de dividir e conquistar. Ele divide uma array de tamanho n em duas arrays de tamanho n/2, as ordena e, depois, as mistura
Essas duas arrays também são dividias em arrays com metade de seus tamanhos para serem ordenadas e misturadas. Essas subarrays também. E assim segue recursivamente até que sejam misturadas duas arrays de tamanho 1
A mistura das arrays é feita comparando elementos de determinados index, começando dos primeiros
O menor é incluso em uma nova array, e seu index é incrementado para que o elemento seguinte seja comparado com o da outra array
Essas comparações se repetem até que todos os elementos de uma array sejam incluídos na nova, aí os elementos restantes da outra são agrupados com o resto
Mergesort é um algoritmo extremamente eficiente em termos de tempo, sendo da classe logaritmica
-
-
-
A eficiência desses algoritmos é medida por uma fórmula chamada general-divide-and-conquer recurrence (recursão geral de dividir-e-conquistar)
Essa fórmula depende de duas contantes que representam em quantos subproblemas o algoritmo pode ser dividido e quantos deles precisam ser resolvidos
É possível determinar a eficiência do algoritmo sem resolver a recursão através do Teorema Mestre, que determina a classe da ordem de crescimento do algoritmo a partir de uma comparação entre as constantes