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.