Please enable JavaScript.
Coggle requires JavaScript to display documents.
Quicksort - Coggle Diagram
Quicksort
Para que seja mais eficiente
Fazer insertion sort nos subarrays pequenos
Pivô deve ser a mediana do mais à esquerda, do meio e mais à direita
Modificar o algoritmo de partição pra um de três partições (menor que, igual à, maior que)
Pseudocódigo de quicksort
Partição de Lomuto
Alternadamente, podemos particionar A [0..n - 1] e, de forma mais geral, o subarray [l..r] (0 ≤ l <r ≤ n - 1)
Começa selecionando um pivô
Faz a varredura do array nas extremidades
Varre da direita para a esquerda (j) para achar um elemento de menor valor que o pivô. Da esquerda para a direita se faz ao contrário.
Depois da varredura podem surgir três situações.
Se i e j se cruzaram: temos subarray particionado
depois de trocar o pivô pelo A[j].
Se i = j: os dois valores indicam um elemento de valor igual ao pivô (subarray particionado).
Se i e j não se cruzaram: trocamos as posições A[i] e A [j] e reiniciamos o escaner com i + 1 e j -1.
(Um elemento em relação a cujo valor dividimos o subarray)
Pior caso
Todas as divisões tiverem subarray vazio
Melhor caso
Todas as divisões acontecem no meio do subarray
Algoritmo de classificação baseado na abordagem divide-and-conquer
Divide os elementos de entrada de acordo com seu valor