Please enable JavaScript.
Coggle requires JavaScript to display documents.
Quicksort - Coggle Diagram
Quicksort
Complexidade
Melhor caso
Θ(nlogn)
Caso medio
1.39 nlogn
Pior caso
Θ(n2)
Pivô
O pivô pode ser o primeiro elemento, o último, um elemento aleatório.
Geralmente vai ser escolhido o primeiro elemento
Elementos maiores que o pivô ficaram a direita
Processo é repetido recursivamente até as listas estarem ordenadas
Elementos menores que o pivô ficaram a esquerda
Particionamento
Existem 2 algoritmos para particionar
Lomuto partition
Mantenha um índice (i) que marca a posição do elemento apos o pivô
varra o array
Se o elemento for menor ou igual ao pivô, incremente i e troque o elemento atual com o elemento na posição i.
No final, troque o pivô com o elemento na posição i + n(numero de numeros menos que o pivô)
Horae partition
Usa dois indicies
I começa no início do array.
Movimente I para a direita até encontrar um elemento maior ou igual ao pivô.
Swap I por J
Repetir isso ate I e J se cruzarem
J começa no final do array.
Movimente J para a esquerda até encontrar um elemento menor ou igual ao pivô.
Divide and conquer
Focado na divisão
Divide com base nos valores
Ele organiza os elementos escolhendo um pivô e particionando os dados ao redor desse pivô.