Aula 06 - Quicksort O(nlogn)

Prévia do material em texto

É o algoritmo mais eficiente para busca. Ele pega um elemento pivô e divide o vetor desordenado 
em duas partes: a parte da esquerda, com elementos menores do que o pivô, e a parte da direita, 
com elementos maiores do que o pivô. O pivô, como fica na posição entre essas duas partes já 
estará na posição correta no vetor ordenado. O problema se reduz então em ordenar cada uma das 
duas partes.
Escolhe o pivô, coloca na posição correta e faz o quicksort com cada uma das partes na posição à 
esquerda do vetor (pivo -1 recursivo) e da direita após o pivô (pivô +1 recursivo).
Escolhe o pivô
Menores a esquerda○
Maiores à direita○
Particiona o vetor com base no pivô
Posição final do vetor será a base final.
Estratégia
Algoritmo
quickSort (V, inicio, fim)
Se (inicio < fim) então
pivo = particiona(vet, inicio, fim);
quickSort(vet, incio pivo -1);
quickSort(vet, pivo+1, fim);
{
}
return
Senão
{
}
particiona (V, inicio, fim)
pivo = vet[inicio]
pos = inicio
I = pos + 1
Enquanto (i <= fim) faça
Se (vet[i] < pivo) então
pos = pos + 1;
Se (pos != i) então
Troca o elemento da posição i com o elemento da posição pos
{
}
{
}
i = i + 1;
{
}
Se (pos != inicio) então
Troca o elemnto da posição pos com o elemento da posição inicio
{
}
return pos
{
Semana 05 - Aula 06 - Quicksort O(nlogn)
sexta-feira, 28 de março de 2014 19:13
 Página 1 de COM112 - Algoritmo e Estrutura de Dados II 
return pos
}
0 3 1 5 2 4 3 1 4 2
quickSort(V, 0, 4) → pivô = particiona (V, 0, 4)
pivo = 3
pos = 0 1 2 3 1 4 5 2
i = 1 2 3 4 5 3 1 2 5 4
Troca final 2 1 3 5 4
quickSort(V,0,1) → pivo = particiona (V, 0,1)
pivo = 2
pos = 0 1
I = 1 2
Troca final 1 2
quickSort (V,0,0) (sai da pilha)
quickSort (V, 2, 1) (sai da pilha) // se inicio < fim return 1 2 3 5 4
quickSort (V, 3, 4) → pivo = particiona (V, 3, 4)
pivo = 5
pos = 3 4
i = 4 5
Troca 4 5
quickSort (V, 3, 3) 
quickSort (V, 5, 4)
1 2 3 4 5
 Página 2 de COM112 - Algoritmo e Estrutura de Dados II