Lesson09

Comparação

Pior caso:

Caso médio:

Em tabelas com poucos elementos fora de ordem, quer o Insertion quer o Bubble são quase lineares. Alguns dos melhores algoritmos de ordenação podem ser quadráticos nestes casos. Quando os elementos são grandes e as chaves pequenas, o Selection é linear no número de dados: se tivermos $N$ elementos com tamanho $M$, em que cada comparação tem custo unitário e cada troca tem custo $M$, o custo total será $N^2/2$ para as comparações e $M N$ para as trocas. Assumindo que $M N$ domina, temos que o custo total é proporcional ao tempo necessário para mover os dados. Este tempo piora quer no caso do Insertion quer no caso do Bubble. Mais tarde veremos como resolver este problema através da utilização de ponteiros.

Avaliação experimental

Quer no Insertion quer no Bubble, as trocas ocorrem apenas entre elementos adjacentes e, portanto, se o menor elemento está no final da tabela, são precisos $N$ passos para o colocar na posição correcta. Veremos de seguida como melhorar este comportamento com o algoritmo Shell sort, em que são permitidas trocas entre elementos afastados, ainda que a estratégia seja idêntica à do Insertion e do Bubble.

Shell sort

Um vector diz-se $h$-ordenado se qualquer sequência de números separados por $h$ posições está ordenada. Neste caso o vector é equivalente a $h$ sequências ordenadas entrelaçadas e, o resultado de $h$-ordenar um vector que está $k$-ordenado, é um vector que está $h$-ordenado e $k$-ordenado.

Por exemplo, o vector abaixo está $2$-ordenado:

/*  +----+----+----+----+----+----+----+----+----+----+----+----+----+
 *  |  1 | 15 |  2 | 16 |  3 | 17 |  4 | 18 |  5 | 19 | 11 | 22 | 18 |
 *  +----+----+----+----+----+----+----+----+----+----+----+----+----+
 */

A ideia inerente ao Shell sort é a seguinte:

• rearranjar os dados de forma a que estejam $h$-ordenados;
• usando valores de $h$ grandes é possível mover elementos na tabela distâncias grandes;
• ordenar primeiro para valores de $h$ grandes e depois para valores de $h$ pequenos facilita as últimas ordenações, para valores de $h$ pequenos;
• utilizar este procedimento para qualquer sequência de $h$’s que termine em $1$ produz no final uma tabela ordenada;
• cada passo torna o próximo mais simples.

Implementação

void shellsort(Item a[], int l, int r)
{ 
  int i, j, h;

  /* 1, 4, 13, 40, 121, 364, 1093, 3280, ... */
  for (h = 1; h <= (r-l)/9; h = 3*h+1)
    ;

  /* Execucao para os valores de h, por ordem inversa. */
  for ( ; h > 0; h /= 3) {

    /* Insertion sort com saltos de tamanho h. */
    for (i = l+h; i <= r; i++) {
      int j = i;
      Item v = a[i];

      while (j >= l+h && less(v, a[j-h])) {
        a[j] = a[j-h]; 
        j -= h;
      }
      a[j] = v;
    }
  }
}

Exemplo: A operação num vector de tamanho $150$:

• para cada valor de $h\in\{40,13,4,1\}$, utilizar o Insertion sort para criar $h$ sub-vectores ordenados dentro de vector com tamanho $150$;
• o vector fica $h$-ordenado;
• para $h = 40$ existem $40$ sub-vectores ordenados, cada um com $3/4$ dos elementos;
• para $h = 13$ existem $13$ sub-vectores ordenados, cada um com $11/12$ dos elementos;
• ...
• para $h = 1$ existe $1$ (sub-)vector ordenado, com $150$ elementos.

Exercício 1: Considere o vector:

int a[] = {19, 2, 15, 18, 4, 11, 17, 18, 5, 1, 3, 22, 16};

Indique o conteúdo de a no final de cada passo do algoritmo Shell sort.

Exercício 2: Considere o vector:

int a[] = {16, 8, 4, 19, 20, 5, 13, 11, 6, 12};

Indique qual o conteúdo do vector a durante a execução do Shell sort após o primeiro valor de $h$ ter sido considerado.

Exercício 3: O Shell sort é estável?

Como escolher a sequência de $h$'s?

Esta é uma questão difícil de responder, sendo que já foram estudadas as propriedades de muitas sequências. E é possível mostrar que umas são melhores que outras:

• 1, 4, 13, 40, 121, 364, 1093, 3280, ... (Knuth, $(3^i - 1)/2$)
• 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, ... (Shell, $2^i$)
• 1, 8, 23, 77, 281, 1073, ... ($4^{i+1} + 3\times 2^i + 1$)

A segunda é pior que a primeira, note-se em particular que os elementos nas posições ímpares não são comparados com os elementos nas posições pares até ao passo final. A terceira é melhor do que a primeira (em 20%). Na prática utilizam-se sequências que decrescem geometricamente para que o número de incrementos seja logarítmico. A sequência óptima ainda não foi descoberta.

Complexidade

A complexidade deste algoritmo depende da sequência de $h$'s e a análise rigorosa é desconhecida. No entanto, para as seguintes sequências, temos

• 1, 4, 13, 40, 121, 364, ... $\sim O(N^{3/2})$
• 1, 8, 23, 77, 281, 1073, ... $\sim O(N^{4/3})$
• 1, 2, 3, 4, 6, 9, 8, 12, 18, ... $\sim O(N (\log N)^2)$

Avaliação experimental

Sequências:

• O: 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, ...
• K: 1, 4, 13, 40, 121, 364, ...
• G: 1, 2, 4, 10, 23, 51, 113, 249, 548, ...
• S: 1, 8, 23, 77, 281, ...
• P: 1, 7, 8, 49, 56, 64, 343, 392, 448, 512, ...
• I: 1, 5, 19, 41, 109, 209, 505, 929, ...

Quick sort

O Quick sort foi inventado nos anos 60 por A. R. Hoare. É um dos algoritmos mais estudado e analisado, e muito popular devido à facilidade de implementação e à sua eficiência. Em média, este algoritmo demora $O(N \log N)$ tempo para ordenar $N$ elementos. No entanto, no pior caso, pode demorar $O(N^2)$ tempo para ordenar $N$ elementos e não é estável. Este algoritmo é também sensível a pequenos erros de implementação que, ainda não introduzindo erros severos, podem levar a ineficiências. A biblioteca standard de C oferece uma implementação (optimizada) do Quick sort, qsort.

A ideia inerente ao Quick sort é a seguinte:

• aplicar o método dividir para conquistar para ordenar;
• efectuar a partição dos dados e ordenar as várias partes independentemente (de forma recursiva):
  • particionar os dados, menores para um lado, maiores para outro, e
  • aplicar algoritmo a cada uma das partes usando recursão.

O processo de partição é crítico para evitar partições degeneradas.

Implementação

Ordenação realizada através de partição e aplicação recursiva do algoritmo aos dois subconjuntos de dados daí resultantes.

void quicksort(Item a[], int l, int r) 
{
  int i;

  if (r <= l)
    return;

  i = partition(a, l, r);
  quicksort(a, l, i-1);
  quicksort(a, i+1, r);
}

Partição:

• Recebe vector a e os limites da parte a ordenar, l e r.
• rearranja os elementos do vector de forma a que as três condições seguintes sejam válidas:
  • o elemento a[i], para algum i, fica na sua posição final (i.e., o pivot);
  • nenhum dos elementos de a[l] a a[i − 1] é maior do que a[i];
  • nenhum dos elementos de a[i + 1] a a[r] é menor do que a[i];
  • o processo coloca pelo menos um elemento na sua posição final.
• Após partição, a tabela fica sub-dividida em duas partes que podem ser ordenadas independentemente aplicando o mesmo processo.

int partition(Item a[], int l, int r) {
  int i = l-1;
  int j = r;

  /* a[r] 'e o pivot. */
  Item v = a[r];

  /* Enquanto o iterador da esquerda for menor que o iterador da direita. */
  while (i < j) {

    /* Enquanto a[i]<v avanca com o i para a direita. */
    while (less(a[++i], v));

    /* Enquanto v<a[j] avanca com o j para a esquerda. */
    while (less(v, a[--j]))
      if (j == l) /* O elemento onde se faz a particao pode ser o primeiro! */
        break;

    /* Trocar, se for o caso! */
    if (i < j)
      exch(a[i], a[j]);
  }

  /* Colocar o pivot na posicao i. */
  exch(a[i], a[r]);

  /* Retorna posicao onde ocorreu a particao. */
  return i;
}

Exercício: Suponha que a função partition é invocada com os seguintes argumentos:

int a[] = {10, 2, -2, 13, 14, -1, 7, 5, 0, 6}, l = 0, r = 9;

Indique qual o conteúdo do vector a após a execução da função partition.

Complexidade

Pior caso: vector já ordenado:

• cerca de $N^2/2$ comparações;
• se o vector já estiver ordenado, todas as partições degeneram e a função chama-se a si própria $N$ vezes;
• o número de comparações é dado por $$ \sum_{i=1}^N i = \frac{(N+1)N}{2}$$
• a situação é a mesma se o vector estiver ordenado por ordem inversa.

Notar que, não apenas o tempo necessário para a execução do algoritmo cresce quadraticamente, como o espaço necessário para o processo recursivo é de cerca de $N$, o que é inaceitável para vectores grandes.

Melhor caso: quando cada partição divide o vector de entrada em duas metades iguais:

• número de comparações usadas pelo Quick sort satisfaz a recursão de dividir para conquistar, $T(N)=2 T(N/2) + O(N)$;
• a solução da recorrência (pelo caso 2 do Master theorem) é $T(N) = \Theta(N \log N)$.

Propriedade: Quick sort utiliza em média cerca de $2N \log N$ comparações.

Melhoramentos

O algoritmo pode ainda ser melhorado com alterações triviais:

• A ordenação de sub-vectores de pequenas dimensões pode ser efectuada de forma mais eficiente. A natureza recursiva do Quick sort garante que uma fracção grande dos sub-vectores terão tamanho pequeno.
• Como escolher correctamente o elemento de partição? Aleatoriamente, mediana de três, ou a média de vários elementos.
• Como melhorar o desempenho se os dados tiverem um grande número de chaves repetidas?

Uma vez que o Quick sort é garantido instanciar-se a si próprio múltiplas vezes para vectores pequenos, como observado acima, devemos utilizar o melhor método possível nesta situação: Insertion sort

void quicksort(Item a[], int l, int r) 
{
  int i;

  if(r-l <= M) {
    insertion(a, l, r);
    return;
  }

  i = partition(a, l, r);
  quicksort(a, l, i-1);
  quicksort(a, i+1, r);
}

Merge sort

A ideia inerente ao Merge sort é a seguinte:

• partir sucessivamente ao meio o vector de elementos a ordenar, até obtermos vectores com apenas um elemento;
• aplicar sucessivamente o procedimento de Merge, para gerar um vector ordenado a partir de dois vectores ordenados.

Notar que o segundo passo é simples, porquê?

Implementação

Item aux[maxN];

void merge(Item a[], int l, int m, int r)
{ 
  int i, j, k;
  for (i = m+1; i > l; i--) 
    aux[i-1] = a[i-1];
  for (j = m; j < r; j++)
    aux[r+m-j] = a[j+1];
  for (k = l; k <= r; k++)
    if (less(aux[j], aux[i]))
      a[k] = aux[j--];
    else
      a[k] = aux[i++];
}

void mergesort(Item a[], int l, int r) { 
  int m = (r+l)/2;

  if (r <= l)
    return;

  mergesort(a, l, m);
  mergesort(a, m+1, r);
  merge(a, l, m, r);
}

Exercício: Dado o vector:

int a[] = {3, 5, 10, 8, 11, 1, 2, 4, 14, 13, 7};

Indique qual o conteúdo do vector a durante a execução do Merge sort.

Complexidade

Tempo de execução dado pela recorrência: $$T(N)=2 T(N/2) + O(N)$$ Pelo segundo caso do Master theorem, temos que $T(N) = \Theta(N \log N)$, válido no pior e no melhor casos.

O Merge sort é estável!