Algoritmo: Quick Sort

O Quick Sort, como o nome já diz, é um dos algoritmos de ordenação mais rápidas já desenvolvida. Utiliza uma estratégia de dividir para conquistar e consiste em pegar um elemento pivô e mover todos os elementos maiores que o pivô para um lado e todos os elementos menores para o outro (o qual lado depende se for crescente ou decrescente). 

Uma das razões dele ser rápido é porque a análise começa das duas pontas e vai em direção ao centro, onde geralmente está localizado o elemento pivô. Depois de analisar e mover todos os elementos em relação ao pivô, então divide-se o vetor em duas partes e aplica a mesma técnica nos dois subvetores, até que não seja possível dividir os vetores. 


Por aplicar a mesma técnica diversas vezes, vamos fazer uso da recursividade, e por esse motivo, separamos o algoritmo em uma função própria, como o pseudocódigo abaixo mostra:


01. QuickSort(vet:INTEIRO[],inicio:INTEIRO, fim:INTEIRO):NEUTRO
02. INICIO
03.  var i,j,pivo,aux: INTEIRO
04.  i=inicio
05.  j=fim
06.  pivo=(inicio+fim) DIV 2
07.  ENQUANTO (i<j) FACA
08.   ENQUANTO (vet[i]<vet[pivo]) FACA
09.    i++
10.   FIMENQUANTO
11.   ENQUANTO (vet[j]>vet[pivo]) FACA
12.    j--
13.   FIMENQUANTO
14.   SE (i<=j) ENTAO
15.    aux = vet[i]
16.    vet[i] = vet[j]
17.    vet[j] = aux
18.    i++
19.    j--
20.   FIMSE
21.  FIMENQUANTO
22.  SE(j>inicio) ENTAO
23.   QuickSort(vet,inicio,j)
24.  FIMSE
25.  SE(i<fim) ENTAO
26.   QuickSort(vet,i,fim)
27.  FIMSE
28. FIM
29.
30. PRINCIPAL():NEUTRO
31. INICIO
32.  var vet = {55, 76, 26, 64, 26, 80, 71, 46}
33.  QuickSort(vet,0,vet.tamanho-1)
34. FIM

Vamos ver como funciona, usando o mesmo vetor que usamos para os outros algoritmos:
Primeiro, invocamos a função que vai abranger todo o vetor, ou seja, da posição 0 até 7: 
 
Depois atribuimos as variáveis de controle i e j para marcar o inicio e o final do vetor
 
Em seguida, elegemos o elemento pivô, que geralmente fica no ponto médio. Para achar, pegamos o valor do inicio e do final da parte que estamos vendo, ou seja, 0 e 7. Somamos os dois e dividimos por dois que resultará um quociente 3. Esse elemento será o nosso pivô nesse momento.

Agora começaremos a análise e as trocas até que i e j se encontrem. Como queremos que o vetor fique em ordem crescente, todos os números menores que o pivô devem ficar a sua esquerda e os maiores a sua direita. Então, iniciaremos a busca do i para o primeiro número que seja maior ou igual ao pivo:


Se o primeiro número não foi maior nem igual, verifique o próximo e vai verificando até 
encontrar:
 

Depois que achou um número maior que o pivô para a variável i, agora procuramos um valor menor ou igual ao pivô para a variável j:



Uma vez encontrado ambos valores para i e para j, vamos realizar a troca entre eles da mesma forma que foi feito no Bubble Sort e Selection Sort.
 
Com ambos valores trocados, tanto o i quanto o j avançam uma posição ao centro.
 
Agora, continuaremos com a busca de um número que seja maior ou igual que o pivô para a variável i:
 
O motivo de que um valor igual ao pivô é justamente esse caso, se existir um número menor a direita do pivô, o pivô precisará ser trocado por um número menor. Entretanto, isso não afetará a ordenação caso depois de um novo pivô seja escolhido, um número maior que ele a esquerda já exista. Agora que a nova posição de i foi escolhida, vamos localizar a nova posição de j.

Localizado ambos os valores e as variáveis i e j ainda não se cruzaram, então realiza-se a troca (a imagem vai ser simplicada, mas segue o mesmo esquema de trocas anteriores):
E depois da troca, ambos i e j avaçam uma posição:
As variáveis i e j acabaram de se cruzar, então agora o vetor será dividido em dois, um subvetor que vai de 0 até j, que no caso é 3, e o outro que vai de i (4) até o final (7).
 
Note que o maior número do primeiro subvetor não é maior que o menor número do segundo subvetor, ou seja, não tem números que precisam ser trocado de posição entre os dois subvetores. Agora, aplicamos o mesmo algoritmo para o primeiro subvetor, definindo seu i, j e pivô:
Encontrado os valores, vamos iniciar o processo de procura:
Nesse caso, encontramos de primeira os valores que queríamos. Como i e j não cruzaram, fazemos a troca:
Depois da troca, tanto o i quanto o j avançam uma posição:
Encontrado o próximo número, fazemos a troca e em seguida i e j avançam:
Como i e j se cruzaram, dividimos novamente o subvetor em duas partes, uma do início até o j e outra do i até o final do subvetor:
Apesar desse caso, o primeiro subvetor já estar ordenado, haverá casos em que não estará exato, por isso que é subdividido. Então, é aplicado novamente o algoritmo de Quick Sort para o subvetor [0,1].
Nesse caso, depois de definido o i e j e o pivô é analisado os números. Nesse caso, ambos os números são iguais ao pivô, então haverá uma troca simbólica e i e j avançarão uma posição:
Agora, i e j cruzaram, ou seja a busca acabou. Normalmente agora seria a subdivisão do vetor, mas note que j está no início e o i está no final. Quando isso ocorre, significa que a ordenação daquele subvetor está finalizada, não havendo necessidade de subdividir. Agora o algoritmo vai processar o subvetor [2,3]:
Agora procuraremos os valores para i e j no subvetor. A variável i vai permanecer no local, uma vez que 46 é igual a 46. Enquanto isso,  j avançará uma casa, uma vez que 55 não é menor que 46 e parará também na posição 2.

Nesse caso, o algoritmo tentará trocar, mas sem efeito, já que as posições i e j são as mesmas. então i e j avançarão uma casa, fazendo os dois cruzarem.
Nesse caso, j já ultrapassou o início e o i está no final, indicando que a ordenação dessa parte está finalizada.
Agora, ambos os lados do subvetor[0,3] estão ordenado, assim, o próprio subvetor [0,3] também está concluído:
E agora, o processo se repete para o outro lado do vetor:
Aqui ocorreu algo diferente, a variável i chegou no final, mas o j não. Isso significa que aqui vai acontecer uma divisão, mas uma delas não será necessário analisar. Com isso, só será necessário criar apenas 1 subvetor, aquele que vai do início até o j (vetor[4,6]).
E agora repete o processo:
Aqui, j e i cruzaram antes de j chegar ao inicio, que significa que o vetor será dividido novamente:
 

O algoritmo novamente se aplica nesse subvetor (i=4, j=5 e pivo=4), entretanto nada ocorrerá já que o subvetor já está ordenado. Com isso, o vetor[4,5] é concluído, e por consequência o vetor[4,6] e o vetor [4,7] e fechando o algoritmo para ordenação do vetor principal.