BCM0505-15 - Processamento da Informação

Aula 06 – 11/03

Problema 6.1: Dada uma lista $A=[0\,..n-1]$ de elementos comparáveis, rearranje-os em $A$ de forma que, ao final, $A$ esteja em ordem crescente: $$A[0] \leq A[1] \leq \cdots \leq A[n-1].$$

Ou seja, queremos ordenar a lista $A$.

Nota: Os códigos desta aula, propositadamente, não conterão anotações de tipo para $A$.

Ordenação por Seleção

O algoritmo mais intuitivo talvez seja o de ordenação por seleção. Inicialmente, determine o índice $k$ de um mínimo em $A[0\,..n-1]$. Troque-o de posição com $A[0]$, isto é, $A[0]\leftrightarrow A[k]$. Determine agora um novo índice $k$ de um mínimo em $A[1\,..n-1]$ e faça a troca $A[1]\leftrightarrow A[k]$. Siga determinando índices $k$ de mínimos em $A[i\,..n-1]$ seguidos por trocas $A[i]\leftrightarrow A[k]$, com $i$ avançando em uma unidade até que $i=n-1$ (não há necessidade de busca e troca neste caso).

# Selection Sort: ordenação por seleção.
# Recebe uma lista A[0..n-1] e rearranja os elementos de A na forma A[0] <= A[1] <= ... <= A[n-1].
def selection_sort (A):
  n = len(A)
  for i in range (n-1): # (*)
    k = i
    for j in range (i+1,n):
      if A[k] > A[j]: k = j
    A[i], A[k] = A[k], A[i]

As invariantes em $(*)$ são:

• $A[0\,..i-1]\leq A[i\,..n-1]$,
• $A[0\,..i-1]$ está em ordem crescente.

Não é difícil perceber que o algoritmo acima é não-adaptativo. Isto é, as operações realizadas independem dos dados — e de suas ordens relativas — de entrada. O laço interno for j é executado $n-i-1$ vezes. O laço externo for i é executado $n-1$ vezes. Logo, o número de comparações A[k] > A[j] é igual a $$\sum_{i=0}^{n-2} n-i-1 = \sum_{i=1}^{n-1} i = \frac{n(n-1)}{2} = \Theta(n^2),$$ em qualquer caso.

Ordenação por Inserção

Outra ideia consiste em manter o início da lista $A[0\,..i-1]$ sempre ordenado e inserir o elemento $A[i]$ em uma “posição correta,” de forma que $A[0\,..i]$ esteja ordenada após a inserção. Como uma lista com um único elemento está sempre ordenada, o método está bem definido: basta repetir o processo acima para $i=1,2,\ldots,n-1$.

# Insertion Sort: ordenação por inserção.
# Recebe uma lista A[0..n-1] e rearranja os elementos de A na forma A[0] <= A[1] <= ... <= A[n-1].
def insertion_sort (A):
  for i in range (1,len(A)): # (%)
    x = A[i]
    j = i
    while j > 0 and A[j-1] > x: # (&)
      A[j] = A[j-1]
      j -= 1
    A[j] = x

As invariantes em $(\%)$ e $(\&)$ são:

• $(\%)$: $i<n$ e $A[0\,..i-1]$ está em ordem crescente,
• $(\&)$: $j>0$ e $A[j-1\,..i-1]\geq A[i]$.

Observe que se a lista $A$ fornecida já estiver em ordem crescente, a expressão do laço interno while é sempre falsa. Neste caso, o número de comparações A[j-1] > x realizadas é ditada pelo laço externo for i, que é executado $n-1$ vezes. Portanto, no melhor caso, a ordenação por inserção realiza $O(n)$ comparações.

O pior caso ocorre na situação simétrica, em que $A$ é fornecida em ordem estritamente decrescente. Neste caso, o laço interno while é executado $n-i-1$ vezes e o laço externo for i, $n-1$ vezes. Logo, o número de comparações no pior caso é $O(n^2)$.

Ordenação por Intercalação

Considere o seguinte subproblema de intercalação:

Para índices $p<q<r$, temos duas sub-listas $A[p\,..q-1]$ e $A[q\,..r-1]$ já ordenadas e queremos combinar estas duas sub-listas adjacentes de forma que obtenhamos $A[p\,..r-1]$ ordenada ao final.

Podemos resolvê-lo com uma ideia simples. Suponha que temos uma lista auxiliar $B=[0\,..r-p]$ na qual copiamos os elementos em $A[p\,..r-1]$. Utilizamos três variáveis indexadoras: $i$ para $B[0\,..q-p]$, $j$ para $B[q-p+1\,..r-q]$ e $k$ para $A[p\,..r-1]$.

Inicialmente, $i=0$, $j=q-p$ e $k=p$. Enquanto $i<q-p$ e $j<r-p$, verificamos se $B[i]<B[j]$. Em caso afirmativo, copiamos $B[i]$ para $A[k]$ e avançamos $i$ e $k$ em uma unidade. Em caso contrário, copiamos $B[j]$ para $A[k]$ e avançamos $j$ e $k$ em uma unidade. Quando a expressão do laço falhar, uma das sub-listas de $B$ terá sido esgotada. Resta-nos apenas copiar o restante da outra sub-lista nas posições restantes de $A$ à partir de $k$.

O código a seguir implementa essa ideia.

# Merge: intercalação.
# Dada uma sublista A e três índices p < q < r tais que A[p] <= A[p+1] <= ... <= A[q-1]
# e A[q] <= A[q+1] <= ... <= A[r-1], rearranja os elementos em A[p..r-1] de forma que
# A[p] <= A[p+1] <= ... <= A[q-1] <= A[q] <= A[q+1] <= ... <= A[r-1].
def merge (A, p: int, q: int, r: int):
  B = [A[i] for i in range (p,r)]
  i, j, k = 0, q-p, p
  while i < q-p and j < r-p:
    if B[i] <= B[j]:
      A[k] = B[i]
      i += 1
    else:
      A[k] = B[j]
      j += 1
    k += 1
  while i < q-p:
    A[k] = B[i]
    i, k = i+1, k+1
  while j < r-p:
    A[k] = B[j]
    j, k = j+1, k+1    

Python provê um mecanismo para acesso a “fatias” (slices) de listas. Para uma lista $A[0\,..n-1]$ e inteiros $0\leq i,j<n$, a expressão A[i:j] acessa/devolve a sub-lista [A[i], A[i+1], ..., A[j-1]] caso $i<j$, ou [] em caso contrário. Extensões e variações existem e falaremos delas mais tarde. Agora, vamos apresentar uma nova versão da função merge() que se beneficia desta operação. A título de variabilidade, vamos também utilizar o operador + para concatenar duas listas.

def merge_var (A, p: int, q: int, r: int):
  B = A[p:q] + A[q:r]
  i, j, k = 0, q-p, p
  while i < q-p and j < r-p:
    if B[i] <= B[j]:
      A[k] = B[i]
      i += 1
    else:
      A[k] = B[j]
      j += 1
    k += 1
  A[k:r-p] = B[i:q-p] if i < q-p else B[j:r-q]

Podemos, agora, ordenar $A$ via repetidas intercalações.

# Merge Sort: ordenação por intercalação.
# Recebe uma lista A[0..n-1] e rearranja os elementos de A na forma A[0] <= A[1] <= ... <= A[n-1].
def merge_sort (A):
  n, step = len(A), 1
  while step < n:
    for i in range (0, n-step, 2*step):
      merge (A, i, i+step, min(n,i+2*step))
    step *= 2

< a ser escrita >

# Merge Sort: versão recursiva.
# Recebe uma lista A[0..n-1] e rearranja os elementos de A na forma A[0] <= A[1] <= ... <= A[n-1].
def rec_merge_sort (A):
  def rms (A, p, r):
    if p+1 >= r: return
    q = (p+r)//2
    rms (A, p, q)
    rms (A, q, r)
    merge (A, p, q, r)
  rms (A, 0, len(A))

Ordenação por Particionamento

< a ser escrita >

# Partition: separação (partição)
# Recebe uma sublista A[p..r-1] com p < r-1. Rearranja os elementos da sublista de forma 
# que A[p], A[p+1], ..., A[j-1] < A[j] <= A[j+1], A[j+2], ..., A[r-1] e devolve j.
def partition (A, p, r):
  x = A[p]
  i, j = p+1, r-1
  while i <= j:
    while i <= j and x >= A[i]: i += 1
    while i <= j and x  < A[j]: j -= 1 
    if i > j: break
    y = A[i]; A[i] = A[j]; A[j] = y
    i, j = i+1, j-1
  A[p] = A[j]; A[j] = x
  return j

# Quick Sort: ordenação por separação.
# Recebe uma lista A[0..n-1] e rearranja os elementos de A na forma A[0] <= A[1] <= ... <= A[n-1].
def quick_sort (A):
  def qs (A, p, r):
    if p+1 >= r: return
    j = partition (A, p, r)
    qs (A, p, j)
    qs (A, j+1, r)    
  qs (A, 0, len(A))

# Quick Sort: com eliminação da recursão de cauda e controle da altura da pilha.
# Recebe uma lista A[0..n-1] e rearranja os elementos de A na forma A[0] <= A[1] <= ... <= A[n-1].
def better_quick_sort (A):
  def qs (A, p, r):
    while p < r-1:
      j = partition (A, p, r)
      if p-j < r-j:
        qs (A, p, j)
        p = j+1
      else:
        qs (A, j+1, r)
        r = j     
  qs (A, 0, len(A))