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]; # 11
Desempenho
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 += 1
Exercí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 += 1
Exercí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 += 1
Exercí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 += 1
Exercí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 += 1
Exercí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 -= 1
Tal 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); # 5
A 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 y
A 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)