Intercalação e mergesort
Exercícios copiados da página Projeto de Algoritmos em C de Paulo Feofiloff.
Intercalação de listas ordenadas
def intercala1( p, q, r, v):
'''(int, int, int, list) -> None
Recebe uma lista v[p:r] tal que v[p:q] e v[q:r]
são crescentes. Rearranja v[p:r] em ordem crescente
'''
n = r-p # 1
w = [None]*n # 2
i, j = p, q # 3
k = 0 # 4
while i < q and j < r: # 5
if v[i] <= v[j]: # 6
w[k] = v[i] # 6
k += 1 # 6
i += 1 # 6
else:
w[k] = v[j] # 7
k += 1 # 7
j += 1 # 7
while i < q: # 8
w[k] = v[i] # 9
k += 1 # 9
i += 1 # 9
while j < r: # 10
w[k] = v[j] # 10
k += 1 # 10
j += 1 # 10
for i in range(p,r): # 11
v[i] = w[i-p]; # 11Desempenho
A função intercala1() consiste essencialmente em movimentar elementos de v de um lugar para outro: primeiro de v para w e depois de w para v. A função executa
2n
dessas movimentações, sendo n o tamanho da lista v[p:r]. O tempo que intercala1() consome é proporcional ao número de movimentações. Portanto, o consumo de tempo da função é proporcional a n, ou seja, O(n).
Exercício 1
Escreva uma função que receba listas x[0:m] e y[0:n], ambos em ordem crescente, e produza uma lista z[0:m+n] que contenha o resultado da intercalação das duas listas dadas. Escreva duas versões da função: uma iterativa e uma recursiva.
Exercício 2
A função intercala1() está correta quando p é igual a q, ou seja, quando a lista v[p:q] está vazio? E quando a lista v[q:r] está vazio?
Exercício 3
Troque as linhas 8 a 11 da função intercala1 pelas duas linhas a seguir. A função continua correta?
while i < q:
w[k] = v[i]
k += 1
i += 1
for i in range(p,j):
v[i] = w[i-p] Exercício 4
Troque o bloco de linhas 5 a 7 da função intercala1() pelas linhas abaixo. Critique o efeito da troca.
while i < q and j < r:
if v[i] <= v[j]:
w[k] = v[i]
k += 1
i += 1
if v[i] > v[j]:
w[k] = v[j]
k += 1
j += 1Exercício 5
Na função intercala1(), troque o bloco de linhas 3 a 10 pelas linhas abaixo. A função continua correta?
i, j = p, q
for k in range(r-p):
if j >= r or (i < q and v[i] <= v[j]):
w[k] = v[i]
i += 1
else:
w[k] = v[j]
j += 1Exercício 6
Na função `intercala1(), troque o bloco de linhas 5 a 10 pelas linhas abaixo. A função continua correta?
while k < r-p:
while i < q and v[i] <= v[j]:
w[k] = v[i]
k += 1
i += 1
while j < r and v[j] <= v[i]:
w[k] = v[j]
k += 1
j += 1Exercício 7
Invariantes. Quais são os invariantes do primeiro while na função intercala1()?
Exercício 8
Critique a seguinte função de intercalação. Ela insere cada elemento de v[q:r] em v[p:q] como o algoritmo de inserção. Observe que a função faz a intercalação in loco , ou seja, sem usar vetor auxiliar.
while q < r:
x = v[q];
i = q-1
while i >= p and v[i] > x:
v[i+1] = v[i]
i -= 1
v[i+1] = x
q += 1Exercício 9
A seguinte solução do problema da intercalação está correta? Quais os invariantes do while? Observe que a função faz a intercalação in loco , ou seja, sem usar vetor auxiliar. Qual o consumo de tempo?
i = p
while i < q and q < r:
if v[i] >= v[q]:
x = v[q]
for k in range(q-1,i-1,-1):
v[k+1] = v[k]
v[i] = x
q += 1
i += 1Exercício 10
Um algoritmo de intercalação é estável se não altera a posição relativa de elementos iguais. A função intercala1() é estável? E se a comparação v[i] <= v[j] for trocada por v[i] < v[j]?
Intercalação com sentinelas
Sedgewick tem uma maneira mais elegante de escrever o algoritmo de intercalação. Primeiro, copia a lista v[p:q] para o espaço de trabalho w[0:q-p]; depois, copia v[q:r] para o espaço w[q-p:r-p] em ordem inversa. Com isso, a metade esquerda de w serve de sentinela para a metade direita durante o processo de intercalação, e vice-versa. Assim, a intercalação de w[0:q-p] com w[q-p:r-p] pode ser feita com base na comparação w[i] <= w[j] sem que seja preciso verificar, a cada iteração, as condições i < q e j ≥ q.
def intercala2(p, q, r, v):
n = r-p
w = [None]*n
for i in range(p,q): w[i-p] = v[i]
for j in range(q,r): w[r-p+q-j-1] = v[j]
i = 0; j = r-p-1
for k in range(p,r):
if w[i] <= w[j]:
v[k] = w[i]
i += 1
else:
v[k] = w[j]
j -= 1Tal como a versão anterior, esta consome tempo proporcional ao tamanho da lista v[p:r.
Mergesort
Agora podemos usar qualquer das funções intercala() discutidas acima para escrever um algoritmo de ordenação, um algoritmo rápido que rearranje qualquer lista v[p:r] em ordem crescente.
O algoritmo é recursivo. A base da recursão é o caso p >= r-1; nesse caso, a lista tem no máximo 1 elemento e portanto não é preciso fazer nada.
def mergesort (p, r, v):
'''(int, int, list) -> None
A função mergesort rearranja a list v[p:r] em ordem crescente.
'''
if p < r-1: # 1
q = (p + r)//2 # 2
mergesort(p, q, v); # 3
mergesort(q, r, v); # 4
intercala (p, q, r, v); # 5A estratégia utilizada pelo mergesort() é conhecida como divisão e conquista.
Exercício 11
Mostre que p < q < r no fim da linha 2 de mergesort.
Exercício 12
Que acontece se trocarmos (p+r)//2 por (p+r-1)//2 no código da função mergesort()? Que acontece se trocarmos (p+r)/2 por (p+r+1)//2?
Exercício 13
Submeta um vetor indexado por [1:5] à função mergesort(). Teremos a seguinte sequência de invocações da função:
mergesort (1,5,v)
mergesort (1,3,v)
mergesort (1,2,v)
mergesort (2,3,v)
mergesort (3,5,v)
mergesort (3,4,v)
mergesort (4,5,v)(observe a indentação). Repita o exercício com um vetor indexado por [1:11].
Exercício 14
A função mergesort é estável?
Exercício 15
Esta função promete rearranjar v[p:r] em ordem crescente. A função está correta?
def mergesort1(p, r, v):
if p < r-1:
q = (p + r) // 2
mergesort1(p, q, v)
mergesort1(q, r, v)
intercala(p, q+1, r, v)Exercício 16
Esta função promete rearranjar v[p:r] em ordem crescente. A função está correta?
def mergesort2( p, r, v):
if p < r:
q = (p + r) // 2
mergesort2(p, q, v)
mergesort2(q, r, v)
intercala(p, q, r, v)Exercício 17
Esta função está correta? Ela promete rearranjar v[p:r] em ordem crescente.
def mergesort3( p, r, v):
if p < r-1:
q = (p + r - 1) // 2
mergesort3 (p, q, v)
mergesort3 (q, r, v)
intercala (p, q, r, v)Exercício 18
Suponha que sua biblioteca tem uma função mrg(p, q, r, v) que funciona assim: recebe uma lista v tal que v[p:q+1] e v[q+1:r] são crescentes e rearranja o vetor de modo que v[p:r] fique crescente. Use mrg() para implementar o algoritmo Mergesort.
Exercício 19
Suponha que sua biblioteca tem uma função interc(v, p, q, r) que recebe uma lista v tal que v[p:q] está em ordem crescente e v[q:r] está em ordem crescente e rearranja o vetor de modo que v[p:r] fique em ordem crescente. Qual o menor valor de q que interc() deve aceitar? Qual o maior valor? Use interc() para escrever uma função mrgsrt(v, p, r) que rearranje um vetor v[p:r] em ordem crescente.
Exercício 20
A seguinte função recursiva pretende encontrar o valor de um elemento máximo do vetor v[p:r], não necessariamente ordenado. É claro que o problema só faz sentido se p <= r.
def max (p, r, v):
if p == r: return v[r]
else:
q = (p + r)//2
x = max(p, q, v)
y = max(q+1, r, v)
if x >= y: return x
return yA função está correta? Ela é mais rápida que a função iterativa óbvia? Quantas vezes a função chama a si mesma? Suponha que p e r valem 0 e 6 respectivamente e mostre a sequência, devidamente indentada, das chamadas de max().
Exercício 21
Número de inversões. O número de inversões de uma lista v[0:n] é o número de pares ordenados (i,j) tais que 0 <= i < j < n e v[i] > v[j]. Escreva uma função que calcule o número de inversões de um vetor dado. O consumo de tempo de sua função deve ser proporcional a $\mathttt{n log n}$ no pior caso. Sugestão: utilize a estratégia de divisão e conquista como o mergesort()
Exercício 22
Fatia de soma máxima. Escreva uma função que dada uma lista v[0:n] de números inteiros, encontra uma fatia v[e:d] de soma máxima. Por exemplo, para v = [31, -41, 59, 26, -53, 58, 97, -93, -23, 84] a fatia de soma máxima é v[2:7] que tem soma igual a 187. O consumo de tempo de sua função deve ser proporcional a $\mathttt{n log n}$ no pior caso. Sugestão: utilize a estratégia de divisão e conquista como o mergesort()
(Editado por Lucas Santos - sábado, 18 Nov 2017, 13:23)