Please enable JavaScript.
Coggle requires JavaScript to display documents.
Quicksort - Coggle Diagram
Quicksort
Baseado em Divisão e Conquista
Divide em subarrays
e vai chamando a função e dividindo até ordenar tudo
Escolhe um elemento para ser o pivô
Temos dois ponteiros, um em cada extremidade
um verifica os valores a extrema direita até o pivô (j)
essa varredura pula valores maiores que o pivô
outro verifica os valores a extrema esquerda até o pivô (i)
essa varredura pula valores menores que o pivô
Os ponteiros vão se movendo em direção ao pivô e verificando se os elementos são maiores ou menores em relação ao pivô
Podem acontecer 3 casos quando a varredura para
Se os ponteiros não se cruzarem
trocamos i e j, incrementando i e decrementando j
Se os ponteiros se cruzaram
Trocamos o pivô e dividimos em novos subarrays
i e j iguais ao pivô
trocamos o pivô, a direita serão maiores e da esquerda menores
Eficiência
Cmelhor(n) = n log2 n
Cpior(n) = Theta(o²)
Cmedio ≈ 2n ln n ≈ 1.39n log2 n.