Please enable JavaScript.
Coggle requires JavaScript to display documents.
Quicksort - Coggle Diagram
Quicksort
Um algoritmo da categoria "divide and conquer"
Comparação com o mergesort
Mergesort
Processo de "divide": Imediato
Processo de "conquer": Não imediato
Divide o array com base nas posições dos números
Quicksort
Processo de "divide": Não imediato
Processo de "conquer": Imediato
Divide o array com base no valor dos números
Divide o array com base no valor dos números
Como?
Utiliza o conceito de "partições"
Uma partição é uma divisão do array original, feita seguindo algum determinado algoritmo
A ideia do quicksort é que o array seja particionado ao redor de um ponto chamado de "split", e os subarrays da esquerda e direita do ponto de split também sejam particionados
Pivôs
Para a ideia de partições, utiliza o conceito de pivôs
Pivôs são números que consideramos estarem já em sua posição definitiva no array
Sendo assim, queremos organizar de forma que todos os números a esquerda de um pivô sejam menores do que ele, enquanto que todos os números na direita do pivô sejam maiores do que ele
O algoritmo de partição mais comum é o de Hoare
O particionamento de Hoare escolhe o pivô como sendo o primeiro elemento do array e utiliza dois iteradores
Um iterador vai da esquerda do array até o final
O outro vai do final até a esquerda
Busca elementos menores do que o pivô e para
Fazemos um swap entre os dois
O processo segue até que eles se cruzem ou sejam iguais
Busca elementos maiores do que o pivô e para
A ideia é que cada partição tenha "subpartições" e que o processo continue a acontecer recursivamente até que um caso base aconteça
O caso base é o mesmo do mergesort: Um array unitário
Não há esforço na etapa do "conquer" porque não há a necessidade de fazer merge entre dois arrays diferentes