Please enable JavaScript.
Coggle requires JavaScript to display documents.
QUICKSORT - Coggle Diagram
QUICKSORT
-
Ao contrário do mergesort, que divide seus elementos de entrada de acordo com a sua posição no array, o quicksort os divide de acordo com seu valor.
Uma partição é um arranjo dos elementos do array de modo que todos os elementos à esquerda de algum elemento A[s] sejam menores ou iguais a A[s], e todos os elementos à direita de A[s] sejam maiores ou iguais a ele.
Obviamente, depois que uma partição é alcançada, A[s] estará em sua posição final no array ordenado, e podemos continuar ordenando os dois subarrays à esquerda e à direita de A[s] independentemente.
A diferença para o mergesort é que enquanto no quicksort todo o trabalho acontece na etapa de divisão, sem a necessidade de trabalho para combinar as soluções para os subproblemas, no mergesort a divisão do problema em dois subproblemas é imediata
e todo o trabalho acontece na combinação de suas soluções.
Se os índices de varredura pararem enquanto apontam para o mesmo elemento, ou seja, i = j, o valor para o qual estão apontando deve ser igual a p, assim, temos o subarray particionado, com a posição de divisão s = i = j.
Esse caso pode ser combinado com o caso de índices cruzados (i > j ) trocando o pivô com A[j ] sempre que i≥ j .
O número de comparações chave feitas antes de uma partição ser alcançada é "n + 1" se na varredura
os índices se cruzam e "n" se coincidem.
Se todas as divisões acontecerem no
meio dos subarrays correspondentes, teremos o melhor caso.
No pior caso, todas as divisões serão distorcidas ao extremo: uma dos
dois subarrays estará vazio e o tamanho do outro será apenas 1 a menos que o tamanho do subarray que está sendo particionado.
Esta situação acontecerá, em particular, para arrays crescentes, ou seja, para entradas para as quais o problema já está resolvido.
Desvantagens do quicksort: Não é estável. Ele requer uma pilha para armazenar parâmetros de subarrays que ainda não foram classificados.
Enquanto o tamanho desta pilha pode ser feito em O(log n) sempre ordenando primeiro o menor de dois subarranjos obtidos por particionamento, é pior que a eficiência espacial O(1) do heapsort.
-
A varredura da esquerda para a direita, começa com o segundo elemento. Como queremos elementos
menor do que o pivô para estar na parte esquerda do subarray, esta varredura pula elementos que são menores que o pivô e param ao encontrar o primeiro
elemento maior ou igual ao pivô.
A varredura da direita para a esquerda, começa com o último elemento do subarray. Já que queremos elementos maiores que o pivô estejam na parte direita do subarray, esta varredura salta sobre os elementos que são maiores que o pivô e para ao encontrar o primeiro elemento menor ou igual ao pivô.
Se tivermos um array de elementos iguais, os subarrays teriam tamanhos 0 e n-1, reduzindo o problema.
Se os índices de varredura e j não cruzarem, ou seja, i < j, simplesmente trocamos A[i] e A[j ] e retomamos as varreduras incrementando i e decrementando j, respectivamente.
Se os índices de varredura cruzarem, ou seja, i > j, teremos particionado o subarray depois de trocar o pivô com A[j].