Scribd
Carregar
22 visualizações2 páginas

Pi Tecprog

O documento aborda algoritmos de ordenação e técnicas de busca, destacando a importância de listas ordenadas para a busca binária. Ele compara a eficiência de diferentes algoritmos, como Quick Sort e backtracking, em problemas como a Mochila e Permutação. Além disso, apresenta a estrutura do algoritmo Quick Sort e seu processo de particionamento.

Enviado por

asalunopentagono
Direitos autorais
© © All Rights Reserved
Levamos muito a sério os direitos de conteúdo. Se você suspeita que este conteúdo é seu, reivindique-o aqui.
Formatos disponíveis
Baixe no formato DOCX, PDF, TXT ou leia on-line no Scribd
22 visualizações2 páginas

Pi Tecprog

O documento aborda algoritmos de ordenação e técnicas de busca, destacando a importância de listas ordenadas para a busca binária. Ele compara a eficiência de diferentes algoritmos, como Quick Sort e backtracking, em problemas como a Mochila e Permutação. Além disso, apresenta a estrutura do algoritmo Quick Sort e seu processo de particionamento.

Enviado por

asalunopentagono
Direitos autorais
© © All Rights Reserved
Levamos muito a sério os direitos de conteúdo. Se você suspeita que este conteúdo é seu, reivindique-o aqui.
Formatos disponíveis
Baixe no formato DOCX, PDF, TXT ou leia on-line no Scribd

Quick Merge

Para utilizar Busca Binária lista deve


estar ordenada

Comparação de algoritmos:

f ( n)
lim se n for +∞ f ( n ) é mais rapido ,
n→∞ g (n )

se n for 0 g ( n ) é mais rapido

caso contrrio é equivalente


Mochila mais
leve

Lenhador
Binário
Mochila
backtracking

Cookies
backtracking

QUICK_SORT(A, INICIO, FIM)

SE INICIO < FIM:

INDEX = PATRICIONA(A, INICIO, FIM)

QUICK_SORT(A, INICIO, INDEX)


Permutação QUICK_SORT(A, INDEX + 1, FIM)
backtracking
FIM SE
PARTICIONA(A, INICIO, FIM)

LUGAR_PIVO := INICIO

PIVO := A[INICIO]

PARA J de INICIO + 1 até FIM FAÇA

SE A[J] < PIVO ENTÃO

LUGAR_PIVO = LUGAR_PIVO + 1

TROCAR A[LUGAR_PIVO] com A[J]

FIM SE

FIM PARA

TROCAR A[INICIO] com A[LUGAR_PIVO]

RETORNAR LUGAR_PIVO

FIM ALGORITMO
Subsets
backtracking

Você também pode gostar