Métodos_de_Ordenação_-_Quicksort

MÉTODOS DE ORDENAÇÃO
QUICKSORT

DEFINIÇÃO
• Proposto por Tony Hoare ou C.A.R Hoare (Colombo, 11 de janeiro de 1934) em 1960, Quicksort é um método de ordenação muito rápido e eficiente, baseado na estratégia de “divisão e conquista”, que consiste em dividir recursivamente um problema
“maior” em problemas “menores”, uma vez solucionado os problemas menores, combinam-se as soluções de modo a chegar numa solução final.
• A estratégia de dividir e conquistar no Quicksort funciona da seguinte maneira...

DEFINIÇÃO
1) Particionar um determinado vetor com n elementos em dois subvetores.
2) Ordenar os sub-vetores de forma independente um do outro.
3) Repetir os passos 1 e 2 repetidamente até chegar na solução definitiva do problema.

DEFINIÇÃO
a) O processo começa selecionando-se um “pivô” para se trabalhar em torno dele.
Ex: 9 | 4 | 6 (pivô escolhido)| 8 | 3 | 1 | 7

b) Em seguida o algoritmo deve rearranjar os elementos no vetor de forma que todos os elementos à esquerda do pivô sejam menores ou iguais a ele e todos os elementos à direita, sejam maiores que ele, não necessariamente já de forma a deixar o vetor ordenado.
Ex: 4 | 3 | 1 | 6 (pivô) | 9 | 8 | 7

DEFINIÇÃO
c) Neste momento, sabemos que o pivô escolhido já está na sua posição correta dentro do vetor. Então vamos repetir os procedimentos “a” e “b” (processo conhecido como recursão) nos sub-vetores à esquerda (elementos menores) e à direita
(elementos maiores) do primeiro pivô escolhido.

Ex:

[4 | 3 | 1] | 6 (pivô) | [9 | 8 | 7]

sub-vetor com os elementos menores

sub-vetor com os elementos maiores

DEFINIÇÃO
• Sintetizando, chegamos ao seguinte passo a passo:
[4 | 3 | 1] | 6 (pivô) | [9 | 8 | 7]
[4 (pivô) | 3 | 1] | 6 | [9 | 8 | 7]
[3 (pivô)| 1] | 4 | 6 | [9 | 8 | 7]
[1 (pivô)]| 3 | 4 | 6 | [9 | 8 | 7]
1| 3 | 4 | 6 | [9 (pivô)| 8 | 7]
1| 3 | 4 | 6 | [ 8 (pivô) | 7] | 9
1| 3 | 4 | 6 | [ 7 (pivô) ] | 8 | 9
1| 3 | 4 | 6 | 7 | 8 | 9 (Vetor Organizado)