Please enable JavaScript.
Coggle requires JavaScript to display documents.
SORTINGS - Coggle Diagram
SORTINGS
Tratamento de problemas de ordenação de objetos de qualquer tipo
Bubble sort
Compara elementos adjacentes e vai trocando com o elemento a esquerda caso seja menor, e vai repetindo até a sequência estar ordenada
Escolha inferior pois dependendo da entrada e do problema, não é eficiente.
Selection sort
Nós varremos a lista toda de entrada procurando o menor elemento e trocando pelo primeiro elemento, e depois procurando o próximo menor elemento na [list.size -1] e trocando pelo segundo elemento.
Considera um array
Big Theta de n²
Dividir para conquistar
Baseado na ideia de dividir o problema em pequenas partes e resolve-las independentes e depois juntar tudo no final
Dividir por uma constante, dividir por um fator constante ou dividir pelo tamanho da variável
Por uma constante
O tamanho da instância é reduzida pela mesma constante em cada interação do algoritmo
Por um fator constante
Reduzir a instância do problema pelo mesmo fator constante em cada interação do algoritmo
Geralmente esse fator constante é 2
Big Theta Log n
Pelo tamanho da variável
O padrão do valor da variável varia de uma interação para outra
A maioria dos casos divide o problema na metade, resolve e após tudo junta
Mergesort
Dado um array, aplica o merge dividindo em 2 partes, essas duas partes também serão aplicadas o merge dividindo em mais 2, até virar um array atômico (de apenas 1 elemento). Depois é comparado elemento com elemento em dupla, e devolvido o resultado ordenado para o array de cima.
Após os arrays chegarem quase ao ponto de ter somente dois, eles vão ser comparado elemento a elemento de cada array, e adicionado na head o menor elemento, já retornando um array ordenado
worst case: Big Theta n log n
Insertion sort
Compara o elemento com todos os outros elementos (do 0 até a posição atual)
Big Theta de n²