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