Estrutura de Dados em C/C++Estrutura de Dados em C/C++2012/22012/2

QuicksortQuicksort

Eduardo Bueno e Thiago Mezzomo – Estrutura de Dados em C/C++

Eduardo Bueno e Thiago Mezzomo – Estrutura de Dados em C/C++

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;

QuicksortQuicksort

Eduardo Bueno e Thiago Mezzomo – Estrutura de Dados em C/C++

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;

Quicksort - ContQuicksort - Cont

Eduardo Bueno e Thiago Mezzomo – Estrutura de Dados em C/C++

É extremamente eficiente para ordenar arquivosde dados.

Necessita de apenas uma pequena pilha comomemória auxiliar.

Quicksort - VantagensQuicksort - Vantagens

Eduardo Bueno e Thiago Mezzomo – Estrutura de Dados em C/C++

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.

Quicksort - DesvantagensQuicksort - Desvantagens

Eduardo Bueno e Thiago Mezzomo – Estrutura de Dados em C/C++

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.

Quicksort – A FunçãoQuicksort – A Função

Eduardo Bueno e Thiago Mezzomo – Estrutura de Dados em C/C++

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.

Quicksort – A FunçãoQuicksort – A Função

Eduardo Bueno e Thiago Mezzomo – Estrutura de Dados em C/C++

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

ReferênciasReferências