MO417 - |
Ata de exercícios |
Ordenação em tempo linear |
Ata - Resolução do exercícios do dia 21/03/2003
|
Organização desta ata:1. Proposta de resolução dos exercícios
|
1. Proposta de resolução dos exercícios |
8.3-4 |
Mostre como ordenar n inteiros no intervalo de 0 a
![]() |
||
. |
Resolução:
Logo, como é dito no exercício que o maior inteiro existente no vetor tem valor ![]() ![]() Substituindo esse valor na fórmula no lugar de b no Lemma 8.4 obtemos: ![]() Escolhendo o valor de r como sendo ![]() ![]() Simplificando: ![]() Resultando em: ![]()
|
8.4-2 | Qual é o tempo de execução do pior caso para o algoritmo de bucket sort ? Que alteração simples no algoritmo preserva seu tempo de execução esperado linear e torna seu tempo de execução no pior caso igual a O(n * lg(n)) ? |
. |
Resolução:
Isso acaba fazendo com que o algoritmo do bucket sort acabe gastando ![]() ![]() Segunda parte da questão)
|
Problema 8-2 |
Vamos supor que temos um arranjo de n registros de dados para ordenar e que
a chave de cada registro tem o valor 0 ou 1. Um algoritmo para ordenar tal conjunto
de registros poderia ter algum subconjunto das três características desejáveis a seguir:
|
||||||
. |
a. Dê um algoritmo que satisfaça aos critérios 1 e 2 anteriores.
b. Dê um algoritmo que satisfaça aos critérios 1 e 3 anteriores.
|
2. Lemas ou algoritmos referenciados nos exercícios |
Lema 8.4 |
Dados n números de b bits e qualquer inteiro positivo r <= b, RADIX-SORT ordena corretamente esses números no tempo ![]() |
. |
Algoritmo Bucket sort | |
1 n = comprimento[A] 2 for i = 1 to n 3 do inserir A[i] na lista ![]() 4 for i = 0 to n - 1 5 do ordenar lista B[i] com ordenação por inserção 6 concatenar as listas B[0], B[1], ..., B[n-1] juntas em ordem |
Algoritmo Insertion sort | |
1 for j = 2 to comprimento[A] 2 do chave = A[j] 3 Inserir A[j] na sequência ordenada A[1..j-1]. 4 i = j - 1 5 while i > 0 e A[i] > chave 6 do A[i + 1] = A[i] 7 i = i - 1 8 A[i + 1] = chave |
Algoritmo Partition | |
1 x = A[r] 2 i = p - 1 3 for j = p to r - 1 4 do if A[j] <= x 5 then i = i + 1 6 trocar A[i] = A[j] 7 trocar A[i+1] com A[r] 8 return i + 1 |
Algoritmo radix sort | |
1 for i = 1 to d 2 do usar uma ordenação estável para ordenar o arranjo A sobre o dígito i |