Dividir e conquistar
Fabio Vinicius Goes Amaral
Quicksort e Multiplicação de números grandes
Novembro, 2015 1 FCT UNESP
Paradigma
• O paradigma de dividir para conquistar parte
do princípio de que é mais fácil resolver vários
problemas menores do que um problema
muito grande
• Dividir o problema até chegar em um caso
simples
Novembro, 2015 2 FCT UNESP
QuickSort
• Método de ordenação muito utilizado
• Depende de um numero do vetor, chamado
de pivô
• Melhor caso: o pivô é o elemento médio
• Pior caso: o pivô é o maior ou o menor
elemento
Novembro, 2015 FCT UNESP 3
Quicksort: Procedimentos
• Escolhe um numero do vetor para ser o pivô
• Percorre o vetor da esquerda para direita até
encontrar um elemento que seja maior que o
pivô
• Percorre o vetor da direita para esquerda até
encontrar um elemento que seja menor que o
pivô
• Troca os elementos encontrados
Novembro, 2015 FCT UNESP 4
Quicksort: Procedimentos
• Ao final, todos os elementos mais a esquerda
serão menores que o pivô e todos os
elementos mais a direita serão maiores que o
pivô
• O pivô estará na posição correta
• Repetir o processo com os dois conjuntos que
estão desordenados (esquerda e direita)
Novembro, 2015 FCT UNESP 5
评论0