Please enable JavaScript.
Coggle requires JavaScript to display documents.
Quicksort - Coggle Diagram
Quicksort
Escolhe-se um elemento do array A[s] para particionar os elementos
À esquerda de A[s] colocam-se todos elementos menores ou iguais a A[s]
À direita colocam-se todos os elementos maiores ou iguais a A[s]
Desta forma, A[s] já se encontrará em sua posição final no array. Agora se realiza a partição nos outros dois subarrays independentemente, encontrando novos A[s]'s em cada um deles
Utilizando este método, ao fim dele, os arrays já estarão ordenados. Não é preciso combinar uma solução
Selecionando o pivot da partição
Primeiro seleciona-se o primeiro elemento do array ou subarray p = A[l] ou A[0]
Varre-se o array, da esquerda pra direita, comparando os elementos com o pivot. (Index i)
Queremos elementos menores do que o pivot na parte esquerda, então ignoramos estes na varredura
Para ao encontrar o primeiro elemento maior ou igual ao pivot.
Começa uma nova varredura da direita pra esquerda, no último elemento do array. (Index j)
Queremos elementos maiores do que o pivot na parte direita do array, então ignoramos estes na varredura
A varredura para ao encontrar o primeiro elemento maior ou igual ao pivot
Temos agora 3 situações possíveis
Se i e j não se cruzaram (i < j), nós trocamos A[i] por A[j] e continuamos as varreduras incrementando i e decrementando j
Se i e j se cruzaram (i > j), nós particionamos o array depois de trocarmos A[j] pelo pivot
Se a varredura para quando i = j, então ambos estarão apontando para o pivot. Então já temos o array particionado, com a posição de split s = j = i.
1 more item...
Solução do inventor!
Partição de Hoare
Mergesort divide os arrays de acordo com posição dos elementos
Quicksort divide de acordo com valores
Desvantagem do quicksort: ele é instável.
Ele precisa de uma pilha para guardar os parâmetros dos subarrays sendo ordenados
Dividir para conquistar!