Separação e quicksort
Exercícios copiados da página Projeto de Algoritmos em C de Paulo Feofiloff.
Quicksort é um outro exemplo de algoritmo inspirado na estratégia de divisão e conquista
O problema da separação
O núcleo do algoritmo Quicksort é o seguinte problema da separação (= partition subproblem), que formularemos de maneira propositalmente vaga:
rearranjar uma lista
v[p:r]
de modo que todos os elementos pequenos fiquem na parte esquerda do vetor e todos os elementos grandes fiquem na parte direita.
Exercício 1
Positivos e negativos. Escreva uma função que rearranje uma lista v[p:r]
de números inteiros de modo que tenhamos v[p:j] <= 0
e v[j:r] > 0
para algum j
em [p:r+1]
. Faz sentido exigir que j
esteja em [p:r]
? Procure escrever uma função rápida que não usa lista auxiliar. Repita o exercício depois de trocar "v[j:r] > 0"
por "v[j:r] >= 0"
. Faz sentido exigir que v[j]
seja 0
?
Exercício 2
Critique a seguinte tentativa de resolver o problema da separação:
def sep (v, p, r):
for i in range(p+1,r):
if v[p] > v[i]:
v[i], v[p] = v[p], v[i]
return p
Exercício 3
Critique a seguinte solução do problema da separação:
def sep (v, p, r):
w = [None]*1000
i = p
j = r
x = v[p]
for k in range(p+1, r):
if v[k] <= x:
w[i] = v[k]
i += 1
else
w[j] = v[k]
j -= 1
// agora i == j
w[i] = x;
for k in range(p, r): v[k] = w[k]
return i
Exercício 4
Um programador inexperiente afirma que a seguinte função rearranja qualquer lista v[p:r]
(com p < r
) de tal forma que v[p:i+1] <= v[i+1:r]
para algum i
em [p:r]
.
def sep (v, p, r):
i, q, j = p, (p + r) // 2, r
while i <= j:
while v[i] < v[q]: i += 1
while v[j] > v[q]: j -= 1
if i <= j:
v[i], v[j] = v[j], v[i]
i += 1
j -= 1
return i
Mostre um exemplo em que essa função não dá o resultado prometido. E se trocarmos "return i"
por "return i-1"
? É possível fazer algumas poucas correções de modo que a função dê o resultado esperado?
Exercício 5
Digamos que uma lista v[p:r]
está separada se existe j
em [p:r]
tal que v[p:j] <= v[j] < v[j+1:r]
. Escreva uma função que decida se v[p:r]
está separada. Em caso afirmativo, a sua função deve retornar o índice j
. Qual o consumo de tempo de sua função?
O algoritmo da separação
Paulo Feofiloff prefere implementar a função separa()
da seguinte maneira a fim de facilitar a análise de sua correção:
def separa (v, p, r):
'''(list, int, int) -> int
Recebe uma lista v[p:r] com p <= r.
Rearranja os elementos da lista e retorna j em [p:r]
tal que `v[p:j] <= v[j] < v[j+1:r].
'''
x = v[p] # x é chamado pivô
i = p+1
j = r-1
while i <= j: #A#
if v[i] <= x: i += 1
elif x < v[j]: j -= 1
else:
v[i], v[j] = v[j], v[i]
i += 1
j -= 1
# agora i == j+1
v[p], v[j] = v[j], x
return j
Em #A#
vale que v[p:i] < x < v[j+1:r]
.
Na aula fizemos a função separa()
que está no livro Introduction to Algorithms de Cormen, Leiserson, Rivest e Stein. Os autores atribuem essa outra versão a N. Lomuto.
Desempenho do algoritmo da separação.
Quanto tempo a função consome? O consumo de tempo é proporcional ao número de comparações entre elementos da lista. Não é difícil perceber que esse número é proporcional ao tamanho r - p
da lista.
Exercício 6
Mostre o resultado da operação separa(v, 0, 15)
, sendo v[0:16] a lista
[33, 22, 55, 33, 44, 22, 99, 66, 55, 11, 88, 77, 33, 88, 66, 66]
Exercício 7
Qual o resultado da função separa()
quando os elementos de v[p:r]
são todos iguais? E quando v[p:r]
é crescente? E quando v[p:r]
é decrescente? E quando cada elemento de v[p:r]
tem um de dois valores possíveis?
Exercício 8
Versão recursiva. Escreva uma versão recursiva da função separa()
.
Exercício 9
Reescreva o código de separa de modo que v[r-1]
seja escolhido para servir de pivô.
Exercício 10
A função separa()
produz um rearranjo estável da lista, ou seja, preserva a ordem relativa de elementos de mesmo valor?
Exercício 11
Critique a seguinte variante da função separa:
def separa (v, p, r):
x, i, j = v[p], p+1, r-1
while i <= j:
if v[i] <= x: i += 1
else:
v[i], v[j] = v[j], v[i]
j -= 1
v[p], v[j] = v[j], x
return j
Exercício 12
Critique a seguinte variante da função separa:
def separa (v, p, r):
x, i, j = v[p], p+1, r-1
while i <= j:
if v[i] <= x:
v[i-1] = v[i]
i += 1
else:
v[i], v[j] = v[j], v[i]
j -= 1
v[j] = x
return j
Quicksort básico
Agora que resolvemos o problema da separação, podemos cuidar do Quicksort propriamente dito. O algoritmo usa a estratégia da divisão e conquista e tem a aparência de um Mergesort "ao contrário":
def quicksort (int v[], int p, int r)
''' Esta função rearranja qualquer lista v[p:r] em ordem crescente. '''
if p < r-1: # 1
j = separa(v, p, r) # 2
quicksort(v, p, j) # 3
quicksort(v, j+1, r) # 4
Exercício 13
Que acontece se trocarmos "p < r-1"
por "p != r-1"
no quicksort()
? Que acontece se trocarmos "j"
por "j+1" na linha 3 do código? Que acontece se trocarmos
"j+1"por
"j"` na linha 4?
Exercício 14
Escreva uma função com protótipo quick_sort(v)
que rearranje uma lista v
em ordem crescente. (Basta invocar quicksort()
da maneira correta.)
Exercício 15
Submeta a lista [77, 55, 33, 99]
indexada por [1:5] à função quicksort()
. Teremos a seguinte sequência de chamadas da função:
quicksort (v,1,5)
quicksort (v,1,3)
quicksort (v,1,1)
quicksort (v,2,2)
quicksort (v,4,5)
Observe a indentação. Repita o exercício com a lista [55, 44, 22, 11, 66, 33]
indexado por [1:7]
Desempenho do Quicksort básico
O consumo de tempo da função quicksort()
é proporcional ao número de comparações entre elementos da lista. Se o índice j
retornado por separa()
estiver sempre mais ou menos a meio caminho entre p
e r
, o número de comparações será aproximadamente n log n
, sendo n
o tamanho r-p
da lista. Por outro lado, se o vetor já estiver ordenado ou quase ordenado, o número de comparações será aproximadamente $\mathttt{n^2}$.
Portanto, o pior caso do quicksort()
não é melhor que o dos algoritmos elementares. Felizmente, o pior caso é muito raro: em média, o consumo de tempo do quicksort()
é proporcional a n log n
.
Exercício 16
[Pedro Rey] A seguinte função promete rearranjar uma lista v[p:r]
em ordem crescente. Mostre que a função está correta. Estime o consumo de tempo da função.
def psort (v, p, r):
if p >= r-1: return
if v[p] > v[r-1]:
v[p], v[r-1] = v[r-1], v[p]
psort (v, p, r-1)
psort (v, p+1, r)
Exercício 17
k-ésimo. Um elemento x
é o k-ésimo menor elemento de uma lista v[0:n]
se em um rearranjo crescente de v
x
é o valor na posição v[k-1]
. Escreva uma função que encontra o k
-ésimo menor elemento de uma dada lista.