Estrutura de Dados em C/C++
2012/2
Quicksort
Eduardo Bueno e Thiago Mezzomo – Estrutura de Dados em C/C++
Quicksort
Proposto por Hoare em 1960 e publicado em1962;
Considerado o algoritimo de ordenação mais rápido;
Não existem dados que comprovem, mas
provavelmente é o mais utilizado;
Eduardo Bueno e Thiago Mezzomo – Estrutura de Dados em C/C++
Quicksort - Cont
 Utiliza a técnica de “dividir para conquistar”;
Divide em duas partes menores com n elementos;
 Cada parte é ordenada independentemente;
Os resultados são combinados produzindo um
resultado final;
 A parte mais delicada do método é o processo de
partição;
Eduardo Bueno e Thiago Mezzomo – Estrutura de Dados em C/C++
Quicksort - Vantagens
 É extremamente eficiente para ordenar arquivos
de dados.
Necessita de apenas uma pequena pilha como
memória auxiliar.
Eduardo Bueno e Thiago Mezzomo – Estrutura de Dados em C/C++
Quicksort - Desvantagens
O método não é estável.
Sua implementação é muito delicada e difícil:
Um pequeno erro pode levar a um resultado não
desejado para algumas entradas de dados.
Eduardo Bueno e Thiago Mezzomo – Estrutura de Dados em C/C++
Quicksort – A Função
Escolha arbitraria de um pivô x.
Percorrer o vetor a partir da esquerda até que A[i] ≥ x.
Percorrer o vetor a partir da direita até que A[j] ≤ x.
Troque A[i] com A[j].
Continue este processo até i e j se cruzarem.
Eduardo Bueno e Thiago Mezzomo – Estrutura de Dados em C/C++
Quicksort – A Função
No final :
Os itens em A[esq], A[esq + 1], ..., v[j] são menores ou
iguais a x;
Os itens em A[i], v[i + 1], ..., A[dir] são maiores ou
iguais a x.
Eduardo Bueno e Thiago Mezzomo – Estrutura de Dados em C/C++
Referências
http://homepages.dcc.ufmg.br/~cunha/teaching/20121/
aeds2/quicksort.pdf
http://www.cplusplus.com/forum/beginner/9388
/
http://w3.ualg.pt/~hshah/ped/Aula%2014/Quick_
final.html
Eduardo Bueno e Thiago Mezzomo – Estrutura de Dados em C/C++