ordenação

Métodos de Ordenação
Métodos Básicos
 Bubblesort
 Seleção Direta
 Inserção Direta
Métodos Avançados
 Quicksort
 Shellsort
 Heapsort

Ordenação Rápida (QuickSort)
• É considerado um dos algoritmos mais eficientes
• Consiste em particionar a tabela a ser ordenada em dois subconjuntos, um à esquerda e outro à direita, de tal forma que todos elementos à esquerda sejam menores que qualquer elemento à direita
• Cada subconjunto é reparticionado segundo o mesmo critério, e assim sucessivamente • O particionamento ocorre a partir da identificação de um elemento da tabela, chamado de chave
• A partir da chave determina-se a correta posição das demais chaves, comparando-as com ele.
Compara a chave com i e j, queremos elementos menores que a chave em i e elementos maiores que a chave em j.
Caso o elemento em i seja menor que a chave o índice i é incrementado
(i++), caso contrário, o índice i fica esperando um elemento j para ser trocado com ele.
Caso o elemento em j seja maior que a chave o índice j é decrementado
(j--), caso contrário, o índice j fica esperando um elemento i para ser trocado com ele.
Quando temos um elemento i e um elemento em j que precisam ser trocados ocorre a troca. Isto é feito enquanto i < j. Quando esta condição não é mais satisfeita compara-se o elemento de j com a chave e é realizada a troca.

Chave = 59

59 34 71 11 97 2 74 7 65 37 i j

1

Troca

59 34 71 11 97 2 74 7 65 37 i j

59 34 37 11 97 2 74 7 65 71 i j

59 34 37 11 97 2 74 7 65 71 i 59 34 37 11

j

7

2

74 97 65 71

i

59 34 37 11

7

2 j 2

Troca

j

74 97 65 71 i 34 37 11

i>=j

7

59 74 97 65 71

Após a primeira execução da técnica temos a primeira divisão do vetor na chave 59. Temos agora dois vetores que passarão pelo mesmo processo.
Um vetor com os elementos antes do 59 e outro com os elementos depois do 59.
A próxima chave será o valor 2.
2

34 37 11

7

Como não