quicksort

UNIVERSIDADE ESTADUAL DE MARINGÁ
DEPARTAMENTO DE INFORMÁTICA

Quicksort – ordenação rápida Prof. Yandre Maldonado - 1

Prof. Yandre Maldonado e Gomes da Costa

Quicksort – ordenação rápida
Métodos de ordenação interna:
Simples: complexidade média O(n2);
Eficientes: complexidade média O(n log n);

Simples:
Prof. Yandre Maldonado - 2

Inserção;
Seleção;
Troca (bolha);

Eficientes:
Shell (ou shellsort);
Quick (ou quicksort);
Heap (ou heapsort).

Quicksort – ordenação rápida

Prof. Yandre Maldonado - 3

Método proposto por C. A. Hoare, em
1962, na Universidade de Moscou;
É considerado o método de ordenação mais eficiente até hoje;
Utiliza a estratégia “dividir para conquistar”; Dividir um problema em subproblemas menores e combinar as soluções a fim de se obter a solução do problema original;

1

Quicksort – ordenação rápida
O método consiste em:

Prof. Yandre Maldonado - 4

Escolher um pivô inicial x;
Colocar todos itens com chave menor que a de x à esquerda de x, formando uma seqüência S1;
Colocar todos itens com chave maior que a de x à direita de x, formando uma seqüência
S2;
Isto feito, o mesmo processo é aplicado às seqüências S1 e S2, que por sua vez produzirão novos segmentos;
O processo deve ser aplicado sucessivamente às seqüências enquanto elas tiverem tamanho ≥ 1.

Quicksort – ordenação rápida
Exemplo de ordenação:

Prof. Yandre Maldonado - 5

Como pivô inicial, o ideal seria adotar a chave mediana da seqüência;
Entretanto, supondo que a seqüência deve estar distribuída aleatoriamente, será adotado o primeiro elemento da seqüência como pivô, inicialmente ele é copiado para uma variável auxiliar x;
Escolhida da chave da posição 0 como pivô
(variável x), esta posição será considerada vazia; 0

x 50

1

2

5

3

4

5

6

7

8

27 88 43 91 71 51 48

↑
I

↑
F

Quicksort – ordenação rápida
Exemplo de ordenação:
Observe ao lado direito do vetor o valor da