trabalho

Ordenação: QuickSort
Prof. Túlio Toffolo http://www.toffolo.com.br BCC202 – Aula 16
Algoritmos e Estruturas de Dados I

QuickSort
• Proposto por Hoare em 1960 e publicado em 1962.
• É o algoritmo de ordenação interna mais rápido que se conhece para uma ampla variedade de situações.
• Provavelmente é o mais utilizado.

2

QuickSort
• A idéia básica é dividir o problema de ordenar um conjunto com n itens em dois sub-problemas menores.
• Os problemas menores são ordenados independentemente. • Os resultados são combinados para produzir a solução final. 3

QuickSort
• A parte mais delicada do método é o processo de partição. • O vetor v[esq..dir] é rearranjado por meio da escolha arbitrária de um pivô x.
• O vetor v é particionado em duas partes:
• Parte esquerda: chaves ≤ x.
• Parte direita: chaves ≥ x.

4

QuickSort – Partição
• Algoritmo para o particionamento:
• 1. Escolha arbitrariamente um pivô x.
• 2. Percorra o vetor a partir da esquerda até que v[i] ≥ x.
• 3. Percorra o vetor a partir da direita até que v[j] ≤ x.
• 4. Troque v[i] com v[j].
• 5. Continue este processo até os apontadores i e j se cruzarem. 5

QuickSort – Após a Partição
Ao final, do algoritmo de partição:
• Vetor v[esq..dir] está particionado de tal forma que:
• Os itens em v[esq], v[esq + 1], ..., v[j] são menores ou iguais a x;
• Os itens em v[i], v[i + 1], ..., v[dir] são maiores ou iguais a x.

6

QuickSort – Exemplo
• O pivô x é escolhido como sendo:
• O elemento central: v[(i + j) / 2].

• Exemplo:

3

6

4

5

1

7

2

7

QuickSort – Exemplo

3
Primeira
partição
Segunda
partição

6

4

5

1

7

2

3

2

4

1

5

7

6

1

2

4

3

5

7

6

4

5

7

6

.
.
.

Caso especial: pivô já na posição correta

terceira partição 1

2

3

Continua...
8

QuickSort – Exemplo

1

2

3

4

5

7

6

3

2