Please enable JavaScript.
Coggle requires JavaScript to display documents.
3-Way QuickSort - Coggle Diagram
3-Way QuickSort
Vídeos
https://www.youtube.com/watch?v=oYmHH1-f_L0
https://www.youtube.com/watch?v=KpnnNj6xfis
Definições
É um tipo híbrido que está entre o radix sort e o quicksort de 3 vias.
Adota a estratégia de divisão e conquista. A estratégia consiste em rearranjar as chaves de modo que as chaves "menores" precedem as chaves "maiores".
Nesse tipo de classificação, o particionamento do array é feito em partes menores e, em seguida, essas partes menores são tratadas recursivamente.
In place, não usa array auxiliar para ordenar
Não estável
Complexidades
TEMPO
O pior tempo de execução do espaço é o mesmo que a classificação rápida de 2 vias (normal).
Leva O(n) tempo para O(1) chaves únicas. Portanto, é usado quando matrizes com grande número de chaves de classificação duplicadas surgem com frequência.
Se somarmos os custos em cada nível de recursão, teremos uma série aritmética que tem valor O(n²), assim, o algoritmo terá tempo de execução igual à O(n²).
ESPAÇO
No melhor caso e no caso médio O(log²n)
No pior caso O(n)
Implementação
Link Implementação do 3 - Way QuickSort
Mais Links Sobre
https://acervolima.com/3-way-radix-quicksort-em-java/
https://medium.com/@nehasangeetajha/3-way-quick-sort-18d2dcc5b06b
https://www.geeksforgeeks.org/3-way-quicksort-dutch-national-flag/