Algoritmos de Ordenação

Introdução sobre algoritmos de ordenação¶

Ordenação bolha (bubblesort)¶

A ideia do bubblesort é realizar sucessivas trocas de elementos adjacentes que estejam fora de ordem até que todos estejam garantidamente em sua posição correta ordenada. É importante observar que a quantidade máxima de vezes em que um elemento do arranjo se encontre fora de ordem com seu adjacente é $n−1$, sendo $n$ o tamanho do arranjo. Em outras palavras, ele deveria ser trocado com todos os outros elementos do arranjo que não ele próprio e por isso, o laço mais externo do algoritmo é executado $n−1$ vezes. Na primeira iteração, o menor elemento é levado à primeira posição. Na segunda iteração, o segundo menor é levado à segunda posição, e assim por diante.

bubble-sort(a) // n = |a|
for i=1 to n−1
  for j=n down to i+1
    if a[j] < a[j−1]
      swap(a, j, j−1)

• Complexidade de tempo (pior caso e melhor caso): $\Theta(n^2)$, pois a operação de comparação entre elementos acontece sem restrições dentro dos dois laços aninhados.

• Complexidade de espaço (pior caso e melhor caso): $\Theta(1)$, pois usamos apenas uma quantidade constante de memória para variáveis auxiliares além da memória fornecida na entrada.

Ordenação por inserção (insertionsort)¶

A ideia do insertion sort é começar com um subarranjo ordenado e adicionar elemento a elemento em sua posição correta no nesse subarranho ordenado. Ao final, o subarranjo ordenado vai conter todos os elementos do arranjo e portanto, o problema estará resolvido. A analogia para este método é a ordenação de cartas de baralho na mão: a cada carta retirada do monte é posicionado na ordem, em sua posição correta na sequência em construção.

insertion-sort(a) // assuma n como sendo o tamanho de a
for i = 2 to n
  elem = a[i]
  j = i − 1
  while j >= 1 and elem < a[j]
    a[j+1] = a[j]
    j = j − 1
  a[j+1] = elem

• Complexidade de tempo (pior caso): $\Theta(n^2)$, sendo que isso acontece quando a comparação elem < a[j] acontece todas as vezes possíveis a cada iteração do laço exterior, isto é, $i−1$ vezes.
• Complexidade de tempo (melhor caso): $\Theta(n)$, sendo que isso acontece quando a comparação elem < a[j] é feita apenas uma vez a cada iteração do laço exterior, isto é, quando o arranjo já se encontrar ordenado.
• Complexidade de espaço (pior caso e melhor caso): $\Theta(1)$, pois usamos apenas uma quantidade constante de memória para variáveis auxiliares além da memória fornecida na entrada.

Ordenação por intercalação (mergesort)¶

O merge sort é um algoritmo de divisão e conquista que utiliza intercalação para combinar subarranjos ordenados dois a dois em arranjos maiores também ordenados. O processo de intercalação (merge) pode ser feito de forma eficiente em tempo linear partindo da premissa que os arranjos de entrada são fornecidos ordenados.

merge(left, right, a) // |left| = n ; |right| = m ; |a| = n + m
i = 1; j = 1; k = 1

while i <= n and j <= m
  if left[i] < right[j]
    a[k] = left[i]; i = i + 1
  else
    a[k] = right[j]; j = j + 1
  k = k + 1

while i <= n
  a[k] = left[i]; i = i + 1; k = k + 1

while j <= n
  a[k] = right[j]; j = j + 1; k = k + 1

merge-sort(a) // |a| = n
if n == 1 or n == 0 return
mid = floor(n / 2)
left = a[1 ... mid]
right = a[mid+1 ... n]
merge-sort(left)
merge-sort(right)
merge(left, right, a)

• Complexidade de tempo (pior caso e melhor caso): A recorrência desse algoritmo é a seguinte:

$T(n) = \begin{cases} 2T(n/2) + \Theta(n) & n > 1 \\ \Theta(1) & n = 1 \end{cases}$

Pois resolvemos dois subproblemas de metade do tamanho original $n$ ($2T(n/2)$), representando o custo de conquistar; gastamos $\Theta(1)$ para dividir com o problema com uma operação aritmética simples; e gastamos $\Theta(n)$ para criar os dois arranjos intermediários das metades e para intercalá-los (merge).

• Complexidade de espaço (pior caso e melhor caso): $\Theta(n)$, por conta dos dois arranjos das metades que precisam ser alocados para as chamadas recursivas.

Quicksort¶

particiona(a, l, r) // a indexado de l a r, inclusive
pivot = a[r]
i = l - 1
for j = 1 to r-1 
  if a[j] <= pivot 
    i = i + 1 
    swap(a, j, i) // troca elementos de posição
swap(a, i+1, r)
return i+1

quicksort(a, l, r) // a indexado de l a r, inclusive
if l >= r return
p = particiona(a, l, r)
quicksort(a, l, p - 1)
quicksort(a, p + 1, r)

• Complexidade de tempo (pior caso): $\Theta(n^2)$, representando duas partições desbalanceadas, uma com zero elementos e uma com todo o restante de elementos menos o pivot. Se isso acontecer, a cada chamada o problema diminui de apenas uma unidade (o pivot).
• Complexidade de tempo (melhor caso): $\Theta(n\log n)$, representando um particionamento ideal a cada chamada recursiva, isto é, totalmente balanceado.
• Complexidade de espaço: $\Theta(1)$, pois o algoritmo é in-place.

Heapsort¶

O algoritmo se baseia em uma estrutura de dados chamada heap, usada para garantir o acesso ao maior (ou menor) elemento com custo constante. O heap máximo pode ser visualizado como uma árvore binária de chaves que mantém a seguinte propriedade: todo nó filho da árvore é menor ou igual ao seu pai. Uma característica importante dessas estruturas heap é que se houver alguma violação de sua propriedade em um único nó, é possível reorganizar seus itens em um heap válido em tempo $\Theta(\log n)$ – isso é feito através do procedimento max-heapify.

left(i)
return 2*i

right(i)
return 2*i + 1

max-heapify(a, i)
l = left(i); r = right(i)
if l <= a.heapsize and a[l] > a[i]
  largest = l
else
  largest = i
if r <= a.heapsize and a[r] > a[largest]
  largest = r
if not (largest = i)
  swap(a, largest, i)
  max-heapify(a, largest)

build-max-heap(a)
a.heapsize = a.length
for i=a.length/2 down to 1
  max-heapify(a, i)

heap-sort(a)
build-max-heap(a)
for i=a.heapsize down to 2
  swap(a, 1, i)
  a.heapsize = a.heapsize - 1
  max-heapify(a, 1)

• Complexidade de tempo (pior caso): $\Theta(n \log n)$. A complexidade do algoritmo max-heapify é da ordem da altura do nó na posição $i$. O procedimento build-max-heap realiza chamadas ao max-heapify na metade dos nós (a segunda metade sempre serão folhas da árvore binária e portanto, já são heaps válidos!). Por ser uma árvore binária, temos mais nós com altura pequena do que nós com altura grande e portanto, ao somar os custos de max-heapify para cada nó na metade inferior do arranjo, temos um somatório que descresce muito rápido em seus termos, levando a um custo linear $\Theta(n)$. Juntando tudo, o procedimento heap sort realiza $n−1$ chamadas ao procedimento max-heapify e esse custo domina a chamada inicial linear da construção do heap.
• Complexidade de espaço: $\Theta(1)$, pois o algoritmo é in-place.

Ordenação em tempo linear¶

Uma abordagem tradicional em estudo de algoritmos é classificá-los em classes de complexidade assintótica, permitindo a comparação direta entre algoritmos. Uma segunda abordagem complementar é ser capaz de afirmar algo sobre a complexidade de um problema frente a um modelo de computação. Em outras palavras, podemos querer responder o seguinte:

“Dados um modelo de computação e um problema, qual é a complexidade mínima que um algoritmo precisa ter para ser correto em solucionar o problema?”

Veja que a resposta para essa pergunta seria uma afirmação muito mais forte do que dizer algo sobre a complexidade de algoritmos isoladamente, já que ela envolve considerar todos os infinitos e possíveis algoritmos que solucionam um problema. Chamamos isso de limites inferiores para problemas.

Limite inferior para ordenação¶

Se considerarmos um modelo de computação baseado em operações de comparação, podemos ilustrar a operação de qualquer algoritmo de ordenação através de uma árvore de decisão. Uma árvore de decisão é uma árvore binária onde cada nó representa uma comparação feita em algum momento no algoritmo (operação) e as arestas representam as respostas para essas comparações: verdadeiro ou falso. Dessa forma, um caminho da raíz até uma das folhas dessa árvore representa uma execução do algoritmo, ou o conjunto de testes/decisões que o algoritmo toma dependendo da entrada. Veja um exemplo para um algoritmo que ordena três letras:

Podemos generalizar para o problema de ordenação de um arranjo qualquer $[a_1,\cdots, a_n]$ e vamos constatar que as folhas dessa árvore binária de decisão representam possíveis saídas de um algoritmo de ordenação, isto é: $\#folhas \geq n!$, pois cada permutação do arranjo precisa ter uma folha representante, senão o algoritmo seria incorreto! A altura dessa árvore representa exatamente o número de comparações (operações) realizadas em alguma execução, seja lá qual for o algoritmo. Dessa forma, se estimarmos a altura da árvore estaremos na verdade estimando o custo mínimo que um algoritmo de ordenação precisa ter para resolver o problema corretamente para qualquer instância de entrada. Sabemos também que a altura $h$ de uma árvore binária com $k$ folhas é, pelo menos, $log_2(k)$:

Conclusão: Não pode existir nenhum algoritmo para o modelo de computação baseado em comparações que tenha um custo assintótico melhor do que $\Omega(n \log n)$.

Ordenação por contagem (countingsort)¶

A primeira etapa é alocar um arranjo de tamanho $k + 1$ que será usado para contar o número de ocorrências de cada elemento. Com isso, vamos acumular nas posições de $C$ de maneira que $C[i]$ contenha o número de elementos $\leq i$, dessa forma podemos identificar para cada elemento de $A$ a posição exata que ele deve ocupar no arranjo ordenado $B$. Com $C$ iremos então, para cada elemento de $A$ em sua ordem inversa, colocá-lo na sua posição correta em $B$. Toda vez que adicionamos um novo elemento em sua posição correta precisamos decrementar a quantidade de elementos menores ou iguais àquele, para que repetições de um mesmo elemento possam ser posicionadas em suas posições corretas também.

counting-sort(A, B, k)
C = "novo arranjo com k + 1 posições: 0 ... k"
for i = 0 to k
  C[i] = 0
for j = 1 to A.length
  C[A[j]] = C[A[j]] + 1
for i = 1 to k
  C[i] = C[i] + C[i - 1]
for j = A.length down to 1
  B[C[A[j]]] = A[j]
  C[A[j]] = C[A[j]] - 1

Radix sort¶

Bucket sort¶