13-Quick Sort

Introdução

O Quick Sort é um algoritmo de ordenação muito rápido e eficiente que foi elaborado em 1960 por um estudante que ao visitar a Universidade de Moscou tentou elaborar um algoritmo para traduzir um dicionario do inglês para o russo, ordenando as palavras, com uma abordagem que consistia em quebrar o problema em problemas menores que poderiam ser resolvidos mais facilmente, usando a abordagem "dividir para conquistar".

Este algoritmo usa a recursividade para a ordenação, particionando "pedaços" de um vetor. A função de ordenação então deve receber como parâmetro alem do vetor a ser ordenado, a posição inicial e a posição final que marcam o pedaço do vetor que será ordenado por particionamento.

Particiona particiona particiona

O nosso array foi pivotado uma vez. Se ele foi particionado, o elemento que anteriormente ocupava a última posição já foi colocado na posição correta, que será a definitiva.

O Guilherme está na posição que merece. Os demais ainda não. Tanto os elementos que estão posicionados à esquerda, como os que estão à direita do pivô não estão adequados. Talvez, por sorte, algum esteja ocupando a posição correta - como a Ana, por exemplo. Mas não sabemos com segurança... O único que temos certeza é o que rodamos o particiona.

Se o Guilherme está na posição correta e os itens da esquerda não estão, podemos posicionar a Mariana adequadamente? Sabemos como fazer isto. Também sei como reposicionar corretamente a Ana. Se mandarmos particionar o quatro primeiros elementos, aonde a Mariana irá terminar? Na posição certa dela. O mesmo irá acontecer se mandarmos particionar os quatro últimos elementos do array: a Ana ficará na posição certa. Logo, depois que particionamos o array, iremos particionar as duas parte menores.

Vamos começar a particionar a parte da esquerda? O pivô será a Mariana. Ela irá ficar na casinha 2, a posição correta.

Porém, os elementos que ficaram a sua esquerda, estão em posições adequadas? E quem ficou à direita? Não sabemos. Precisaremos rodar o particiona também para quem está posicionado tanto à direita como à esquerda.

Se rodarmos o particiona para estes elementos também, o que acontecerá? Veremos. Iremos particionar o André e o Jonas. Quem será o pivô? O Jonas.

Logo, colocaremos o Jonas no lugar correto.

Agora precisamos pivotear os elementos que estão à esquerda e à direita do Jonas.

Porém, no lado esquerdo do Jonas, não temos elementos. Se o número de elementos é igual a 0, não fará sentido particionar.

No lado direito, temos apenas um elemento. Se temos que ordenar um elemento, também não será preciso reposicioná-lo.

Será o mesmo com a Juliana. Também teremos apenas um elemento e por isso, não iremos reposicioná-la.

Agora iremos particionar os quatro elementos posicionas à direita. Quem será o pivô? A Ana.

Vamos colocá-la no seu lugar! Ela já ocupa a posição adequada.

A Ana está no lugar certo. Em seguida, teremos que particionar a esquerda e a direita do pivô.

Começaremos pelo lado esquerdo. Quem será o novo pivô? O Carlos.

Ao pivotearmos o Carlos, teremos que repetir a ação com os elementos posicionados a sua esquerda e sua direita.

No entanto, à esquerda do Carlos está vazia e só nos resta elementos à direita. Quem será o pivô dos itens restantes? A Lúcia.

A Lúcia está na posição correta. Temos agora que repetir o mesmo processo à sua esquerda e direita.

Vamos particionar o lado esquerdo. Teremos apenas um elemento, logo ele permanecerá no mesmo lugar.

À direita, não haverá elementos, por isso, não precisaremos fazer nada. Faltou um último pivoteamento, novamente de tamanho 0.

O que faremos? Nada, novamente.

O array está completamente ordenado. Nós usamos a sacada de, ao pivotear um elemento, colocávamos em seguida na posição certa. Quando mandávamos ordenar os elementos posicionados à direita e à esquerda do novo pivô, pivoteávamos e ordenávamos os pedaços menores que se formavam. Repetimos o processo até que precisávamos pivotear 0 ou 1, e não era preciso fazer nada. Seguimos por todos elementos, até que array estava ordenado e cada um ocupava a sua posição certa.

Vamos revisar o que fizemos:

Para ordenar de uma posição até a outra, precisamos considerar o número de elementos. Se ele for de 0 até 1, não é preciso fazer nada. Caso ele seja maior, mandamos particionar o pedaço e colocar o pivô na posição adequada. Ordenamos os elementos posicionados às esquerda e à direita do pivô. Em seguida, o algoritmo irá ordenando os trechos menores que irão se formando. Ele seguirá pivoteando, até que todos os elementos estejam todos ordenados.