Please enable JavaScript.
Coggle requires JavaScript to display documents.
Quicksort - Coggle Diagram
Quicksort
Eficiência do Quicksort
A qtde. de comparações feitas antes de a partição estar completa é de n+1 se os índices se cruzarem e n se eles forem iguais.
Se todas as divisões ocorrerem no meio dos subarrays correspondentes, teremos o melhor caso: Cbest(n) = 2Cbest(n/2) + n.
No pior dos casos a divisão vai ao extremo: um dos dois subarrays vai estar vazio, e o tamanho do outro vai ser 1 a menos do que o tamanho do subarray sendo particionado. Esta situação vai acontecer quando o problema já estiver resolvido.
No pior caso a qtde. de comparações feitas será: Cworst(n) = (n+1) + n + ... + 3 = (((n+1)(n+2))/2) - 3 ∈ Θ(n²).
A utilidade do quicksort depende, então, do seu caso normal (average case). Cavg(n) = 1/n ∑ s = 0, n-1, [(n+1) + Cavg(s) + Cavg(n-1-s)] para n > 1.
Assim, em casos normais, o quicksort faz 39% de comparações a mais que no melhor caso.
Após isso, podem ocorrer 3 situações:
Se os índices i e j não se cruzarem, ou seja se i < j, os elementos A[i] e A[j] são trocados e o processo continua.
Se os índices i e j se cruzarem, ou seja, se i > j, significa que o array está particionado, então A[j] é trocado de lugar com o pivô.
Se os índices i e j pararem apontando para o mesmo elemento, ou seja i = j, então A[j] é trocado de lugar com o pivô.
Por causa de sua importância, alguns esforços para refiná-lo foram feitos, algumas das melhorias descobertas por pesquisadores foram:
Melhor seleção do pivô com métodos como randomized quicksort que usa um elemento aleatório, ou o método median-of-three que usa a mediana dos elementos do meio, do começo e do final do array.
Trocar para o insertion sort quando os subarrays estão muito pequenos, ou simplesmente não ordenar esses subarrays e terminar aplicando o insertion sort em todo o "quase" ordenado array.
Modificações na partição do array, como por exemplo, a partição three-way que particiona o array em 3: menor que, igual a, e maior que o pivô.
Um algoritmo "dividir para conquistar", que divide seus elementos de acordo com seu valor, diferente do Mergesort que divide de acordo com sua posição no array.
Ele faz uma partição, que seria uma distribuição dos elementos do array, de modo que à esquerda ficariam os elementos menores que um certo pivô, e à direita os elementos maiores à esse pivô.
Depois que essa primeira partição é concluída, o pivô estaria na sua posição final, então a ordenação (pelo mesmo método) continua para os dois subarrays à esquerda e à direita do pivô.
O array é escaneado usando 2 índices i e j. O i escaneia da esquerda para a direita e para quando encontra um elemento maior ou igual ao pivô. O j escaneia da direita para à esquerda e para quando acha um elemento menor ou igual ao pivô.
De acordo com Robert Sedgewick, essas melhorias em combinação podem diminuir o tempo de execução em 20%-30%.
Como todo algoritmo de ordenação, o quicksort tem seus pontos fracos, ele não é estável, e precisa de uma pilha para guardar parâmetros de subarrays que ainda vão ser armazenados.