Please enable JavaScript.
Coggle requires JavaScript to display documents.
Algoritmos de ordenação pt.2 - Coggle Diagram
Algoritmos de ordenação pt.2
quickSort
Divide-and-conquer
Ideia geral: Divide os elementos de acordo com seus valores.
O array é organizado de modo que à esquerda de um elemento A[s] tenha apenas elementos menores que A[s] e à direita, apenas elementos maiores ou iguais ao A[s].
Quando essa organização é alcançada, A[s] já estará na sua posição final, restando apenas continuar a ordenação dos dois subArrays (esquerda e direita de A[s]).
Obs.: Aqui, todo o trabalho acontece na fase de divisão do problema e o custo de combiná-los é imediato, ao contrário do mergeSort: Nesse, a divisão é imediata e o custo está na combinação.
HoarePartition: Organiza o subArray, uilizando o primeiro elemento como Pivot.
Cbest(n) ∈ Θ(n log2 n)
Cworst(n) ∈ Θ(n²)
(ironicamente, a pior entrada possível para o quickSort é quando o input já está ordenado).
Cavg(n) ≈ 2n ln n ≈ 1.39n log2 n.
(em média, o algoritmo executa apenas 39% operações básicas a mais que no melhor caso, garantindo a utilidade do quickSort mesmo tendo uma ordem de crescimento quadrática como pior caso).
Melhorias sugeridas por pesquisadores
Melhores meios de seleção do pivot: Escolher um elemento aleatório; média dos elementos mais a esquerda, mais a direita e do meio;
Trocar para insertionSort em subArrays muito pequenos (entre 5 e 15 elementos) ou não ordenar de forma alguma os subArrays menores, finalizando com um insertionSort no array quase ordenado.
Fraquezas: Instável, necessita de uma pilha para armazenar parâmetros de subArrays que ainda não foram ordenados, pior caso quadrático (maneiras sofisticadas de seleção do pivot tornam o pior caso pouco provável, mas ainda possível).
binSort
Ideia geral: Separar o input em listas relativamente menores(bins ou buckets), levando em consideração alguma característica dos elementos. Depois dessa separação, feita em uma unica "passada", ordenar cada lista individualmente é mais simples.
Complexidade depende do algoritmo escolhido para os bins/buckets
radixSort
Ideia geral: Processa cada dígito do elemento individualmente, podendo ordenar com base no dígito mais ou menos significativo. No caso do menos significativo, elementos curtos ficam antes dos elementos longos, e elementos de mesmo tamanho são ordenados lexicograficamente.
Não-comparativo: distribui os elementos de acordo com seus 'radix'
Complexidade: Cworst ∈ O(w*n), onde w representa o número de bits necessários para armazenar cada "chave".