Please enable JavaScript.
Coggle requires JavaScript to display documents.
Quicksort - Coggle Diagram
Quicksort
-
-
pseudocode
Antes precisariamos escolher um elemento como pivô, agora, podemos partir da estratégia de selecionar simplismente o primeiro elemento do subarray.
Precisamos verificar ambos os fins de um subarray, e comparar os elementos do subarray com o pivô
Left-to-right
Denotamos o index do ponteiro i.Passamos a verificar cada elemento do subarray mantendo os menores elementos a esquerda e até quando encontramos um elemento igual ou maior que o pivô
Right-to-left
Denotamos o index do ponteiro j, vamos começa com o último elemento do subarray. Desde então, queremos os elementos maiores que o pivô e para-se o processo quando encontrarmos um elemento menor ou igual que o pivô
Depois da verificação parar, há 3 situações possíveis a depender da verificação dos indeces
Se a verificação dos indices i e j não cruzarem, i < j, podemos fazer a mudança A[i] e A[j] e resumir as olhadas por meio de incrementos de i e decrementos de j;
Se a verificação dos indices cruzar, i > j , nós teriamos particionado o subarray depois de ter encontrado o pivô com A[ j ].
Quando a verificação para quando os indices são iguais, logo, temos um subarray particionado com o split posição s = i = j.
-
Como algoritmo de partição, podemos usar o Lomuto partição (Section 4.5) ou de forma genérica subarrays.
Enquanto no Mergesort os elementros e entrada são dividos pela sua posição no array, no quicksort e pelo seu valor