Ordenação: algoritmos elementares

Primeiro coloque os números em ordem.
Depois decidimos o que fazer.

estratégia algorítmica 

Este capítulo trata do seguinte problema fundamental:  Permutar (ou seja, rearranjar) os elementos de um vetor  v[0..n-1]  de tal modo que eles fiquem em ordem crescente, isto é, de tal forma que tenhamos  v[0]  ≤  v[1]  ≤  . . . ≤  v[n-1] .

0 1 2 3 4 5 6 7 8 9 10
111 999 222 999 333 888 444 777 555 666 555
111 222 333 444 555 555 666 777 888 999 999

Discutiremos aqui dois algoritmos simples mas lentos para o problema.  Outros capítulos descreverão algoritmos mais sofisticados e bem mais rápidos.

Embora o problema tenha sido apresentado em termos da ordenação de um vetor, ele faz sentido para qualquer estrutura linear, como uma lista encadeada, por exemplo.

Exercício 1

  1. Importante.  Escreva uma função que verifique se um vetor v[0..n-1] está em ordem crescente.  (Esse exercício põe em prática a estratégia de escrever os testes antes de inventar algoritmos para um dado problema.)
  2. Critique o código da seguinte função, que promete decidir se o vetor v[0..n-1] está em ordem crescente.
    int verifica (int v[], int n) {
       int i;
       if (n > 1) 
          for (i = 1; i < n; i++) 
             if (v[i-1] > v[i]) return 0; 
       return 1; }
    
  3. Critique o código da seguinte função, que promete decidir se o vetor v[0..n-1] está em ordem crescente.
    int verifica (int v[], int n) {
       int i, sim;
       for (i = 1; i < n; i++) 
          if (v[i-1] <= v[i]) sim = 1;
          else {
             sim = 0;
             break; }
       return sim; }
    
  4. Escreva uma função que rearranje um vetor v[0..n-1] de modo que ele fique em ordem estritamente crescente.
  5. Escreva uma função que receba um inteiro x e um vetor v[0..n-1] de inteiros em ordem crescente e insira x no vetor de modo a manter a ordem crescente.

Algoritmo de inserção

Eis um algoritmo de ordenação muito popular, frequentemente usado para colocar em ordem um baralho de cartas:

// Esta função rearranja o vetor v[0..n-1]
// em ordem crescente.

void
insercao (int n, int v[])
{
   int i, j, x;
   for (j = 1; j < n; ++j) {
      x = v[j];
      for (i = j-1; i >= 0 && v[i] > x; --i) 
         v[i+1] = v[i];
      v[i+1] = x;
   }
}

(Compare o loop interno com o algoritmo de inserção discutido no capítulo Vetores.)   Para entender o funcionamento do algoritmo, basta observar que no início de cada repetição do for externo, imediatamente antes da comparação de j com n,

  1. o vetor  v[0..n-1]  é uma permutação do vetor original  e
  2. o vetor  v[0..j-1]  está em ordem crescente.

Essas condições invariantes são trivialmente verdadeiras no início da primeira iteração, quando j vale 1.  No início da última iteração, j vale n e portanto o vetor v[0..n-1] está em ordem, como desejado. (Note que a última iteração é abortada logo no início, pois a condição j < n é falsa.)

0 crescente j-1 j         n-1
444 555 555 666 777 222 999 222 999 222 999

Desempenho do algoritmo de inserção

Quantas vezes a função insercao compara x com um elemento do vetor?  Mais precisamente, quantas vezes, no máximo, a função insercao executa a comparação  v[i] > x?  Esse número está diretamente relacionado com a sequência de valores de i ao longo da execução da função.  Para cada valor de j, a variável i assume, no pior caso, os valores j-1,  . . . ,  0. A seguinte tabela mostra esses valores explicitamente:

j    i
1    0                1  
2    1 0              2  
3    2 1 0            3  
.    . . .            .  
n-1  n-2 n-3 .. 1 0   n-1

A terceira coluna da tabela dá o número de diferentes valores de i na linha.  Portanto, o número de execuções de v[i] > x é, no pior caso, igual à soma da terceira coluna. Essa soma é n(n-1)/2, ou seja, um pouco menos que a metade de

n2 .

Agora considere o tempo que a função insercao consome para fazer o serviço.  Esse tempo é proporcional ao número de execuções da comparação v[i] > x (pense!).  Logo, o consumo de tempo da função cresce, no pior caso, como o quadrado do tamanho do vetor.  Se um vetor de tamanho N consome T segundos então um vetor de tamanho 2N consumirá  4T  segundos e um vetor de tamamanho 10N consumirá  100T  segundos!

Essa análise mostra que o algoritmo de inserção é lento demais para ordenar vetores grandes.  Graças à sua simplicidade, entretanto, o algoritmo é muito útil no caso de vetores pequenos.

(No melhor caso, o desempenho do algoritmo é muito bom:  o número de comparações não passa de  n  e portanto o consumo de tempo é proporcional a  n.)

Animações do algoritmo de inserção

Exercícios 2

  1. Escreva uma versão recursiva do algoritmo de ordenação por inserção. 
  2. Na função insercao, troque a comparação  v[i] > x  por  v[i] >= x.  A nova função continua correta?
  3. Que acontece se trocarmos  for (j = 1  por  for (j = 0  no código da função insercao?  Que acontece se trocarmos  v[i+1] = x  por  v[i] = x?
  4. Critique a seguinte implementação do algoritmo de ordenação por inserção:
    int i, j, x;
    for (j = 1; j < n; ++j) {
       x = v[j];
       for (i = j-1; i >= 0 && v[i] > x; --i) {
          v[i+1] = v[i];
          v[i] = x; } }
    
  5. Critique a seguinte implementação do algoritmo de ordenação por inserção:
    int i, j, x;
    for (j = 1; j < n; ++j) {
       for (i = j-1; i >= 0 && v[i] > v[i+1]; --i) {
          x = v[i]; v[i] = v[i+1]; v[i+1] = x; } }
    
  6. Critique a seguinte implementação do algoritmo de ordenação por inserção:
    int i, j, x;
    for (j = 1; j < n; ++j) {
       x = v[j];
       i = j - 1;
       while (i >= 0 && v[i] > x) { 
          v[i+1] = v[i];
          --i; }
       v[i+1] = x; }
    
  7. Importante.  Escreva uma versão do algoritmo de inserção que rearranje em ordem crescente um vetor v[p..r] e tenha o seguinte invariante: no início de cada iteração, o vetor v[k+1..r] é crescente.
  8. O papel do for interno na função insercao é encontrar o ponto onde v[j] deve ser inserido em v[0..j-1]. Considere fazer isso com uma busca binária. Analise o resultado.
  9. Pior caso.  Descreva e analise uma instância de pior caso para o algoritmo de inserção, ou seja, um vetor v[0..n-1] que leva o algoritmo a executar o maior número possível de comparações.
  10. Melhor caso.  Descreva e analise uma instância de melhor caso para o algoritmo de inserção, ou seja, um vetor v[0..n-1] que leva o algoritmo a executar o menor número possível de comparações.
  11. Movimentação de dados.  Quantas vezes, no pior caso, o algoritmo de inserção copia um elemento do vetor de um lugar para outro?  Quantas vezes isso ocorre no melhor caso?
  12. Testes com vetor aleatório.  Escreva um programa que teste, experimentalmente, a correção de sua implementação do algoritmo de inserção. Use permutações aleatórias de 1..n para os testes. Compare o resultado da ordenação com 1..n.  Aproveite a ocasião para cronometrar o algoritmo de ordenação (use a função clock da biblioteca time).
  13. Escreva uma função com protótipo  insert_sort (int v[], int n)  que rearranje um vetor v[1..n] em ordem crescente. (Basta invocar insercao da maneira correta.)
  14. Escreva uma função que permute os elementos de um vetor v[0..n-1] de modo que eles fiquem em ordem decrescente.

Algoritmo de seleção

Esta seção trata de outro algoritmo de ordenação bem conhecido.  Ele usa a seguinte estratégia: seleciona o menor elemento do vetor, depois o segundo menor, depois o terceiro menor, e assim por diante:

// Esta função rearranja o vetor v[0..n-1]
// em ordem crescente.

void
selecao (int n, int v[])
{
   int i, j, min, x;
   for (i = 0; i < n-1; ++i) {
      min = i;
      for (j = i+1; j < n; ++j)
         if (v[j] < v[min])  min = j;
      x = v[i]; v[i] = v[min]; v[min] = x;
   }
}

Para entender por que o algoritmo está correto, basta observar que no início de cada repetição do for externo, imediatamente antes da comparação de i com n-1, valem os seguintes invariantes:

  1. o vetor  v[0..n-1]  é uma permutação do vetor original,
  2. v[0..i-1] está em ordem crescente e
  3. v[i-1]  ≤  v[i..n-1].

A tradução do terceiro invariante para linguagem humana é a seguinte: v[0..i-1] contém todos os elementos pequenos do vetor original e v[i..n-1] contém todos os elementos grandes.

0 crescente i-1 i         n-1
110 120 120 130 140 999 666 999 666 999 666
pequenos grandes

Os três invariantes garantem que no início de cada iteração v[0], . . , v[i-1] já estão em suas posições definitivas.  No início da última iteração, o vetor está em ordem crescente, como desejado.

Desempenho do algoritmo de seleção

Tal como o algoritmo de inserção, o algoritmo de seleção faz cerca de n2/2 comparações entre elementos do vetor no pior caso.  Diferentemente do algoritmo de inserção, o algoritmo de seleção também faz cerca de n2/2 no melhor caso.  Assim, o consumo de tempo do algoritmo é sempre proporcional a n2.

Em vista dessa análise (e de outras observações que faremos nos exercícios) o algoritmo de inserção é preferível ao de seleção.

Animações do algoritmo de seleção

Exercícios 3

  1. Escreva uma versão recursiva do algoritmo de ordenação por seleção.
  2. Na função selecao, que acontece se trocarmos for (i = 0  por  for (i = 1?  Que acontece se trocarmos for (i = 0; i < n-1  por  for (i = 0; i < n ?
  3. Na função selecao, troque a comparação  v[j] < v[min]  por  v[j] <= v[min].  A nova função continua correta?
  4. Pior caso.  Descreva e analise uma instância de pior caso para o algoritmo de seleção, ou seja, um vetor v[0..n-1] que leva o algoritmo a executar o maior número possível de comparações.
  5. Melhor caso.  Descreva e analise uma instância de melhor caso para o algoritmo de seleção, ou seja, um vetor v[0..n-1] que leva o algoritmo a executar o menor número possível de comparações.
  6. Movimentação de dados.  Quantas vezes, no pior caso, o algoritmo de seleção copia um elemento do vetor de um lugar para outro?  Quantas vezes isso ocorre no melhor caso?
  7. Escreva uma função que permute os elementos de um vetor inteiro v[0..n-1] de modo que eles fiquem em ordem decrescente. Inspire-se no algoritmo de seleção.

Exercícios 4

  1. Ordenação de strings.  Escreva uma função que coloque em ordem lexicográfica um vetor de strings ASCII. Use o algoritmo de inserção.
  2. Ordenação de arquivo.  Escreva uma função que rearranje as linhas de um arquivo ASCII em ordem lexicográfica.  Suponha que todos os caracteres do arquivo pertencem ao alfabeto ASCII. Compare com o utilitário sort.
  3. Ordenação de structs.  Suponha que cada elemento de um vetor é um registro com dois campos: um é um inteiro e outro uma string ASCII:
       struct registro {int aa; char *bb;};
    

    Escreva uma função que rearranje o vetor de modo que os campos aa fiquem em ordem crescente.  Escreva outra função que rearranje o vetor de modo que os campos bb fiquem em ordem lexicográfica.

  4. Desafio.  Invente um algoritmo de ordenação que seja mais rápido que o de inserção e o de seleção.
  5. Embaralhamento aleatório?  Considere a seguinte antítese do problema de ordenação: fazer um embaralhamento aleatório dos elementos de um vetor v[0..n-1], ou seja, rearranjar os elementos do vetor de modo que todas as permutações sejam igualmente prováveis. Discuta e critique a seguinte solução (ela foi usada na distribuição européia do Windows 7 da Microsoft):
    void insercao_aleatoria (int n, int v[]) {
       int i, j, x;
       for (j = 1; j < n; ++j) {
          x = v[j];
          for (i = j-1; i >= 0 ; --i) {
             if (rand() > RAND_MAX/2) 
                v[i+1] = v[i];
             else break; }
          v[i+1] = x; } }
    
  6. Ordenação de lista encadeada.  Escreva uma função que ordene uma lista encadeada. Inspire-se no algoritmo de inserção para vetores.  (Sua função precisa devolver alguma coisa?).
  7. Ordenação de lista encadeada.  Escreva um função para ordenar uma lista encadeada. Imite o algoritmo de seleção para vetores.  (Sua função precisa devolver alguma coisa?).

Exercícios 5: aplicações

Muitos problemas podem ser reduzidos à ordenação de um vetor, ou seja, podem ser resolvidos com o auxílio de um algoritmo de ordenação (não necessariamente um dos algoritmos discutidos neste capítulo).

  1. Anagramas.  Uma palavra é anagrama de outra se a sequência de letras de uma é permutação da sequência de letras da outra.  Por exemplo, aberto é anagrama de rebato.  Digamos que duas palavras são equivalentes se uma é anagrama da outra.  Uma classe de equivalência de palavras é um conjunto de palavras duas a duas equivalentes.  Escreva um programa que receba um arquivo ASCII contendo palavras (uma por linha) e extraia desse arquivo uma classe de equivalência máxima.   Aplique o seu programa a um arquivo que contém todas as palavras do português brasileiro com diacríticos removidos.  (O arquivo é grande; portanto, o seu programa deverá ser muito eficiente.)
  2. Valores distintos.  Dado um vetor v[0..n-1] de números inteiros, determinar quantos números distintos há no vetor (ou seja, determinar o tamanho do conjunto de elementos do vetor).
  3. Mediana.  Seja v[0..n-1] um vetor de números inteiros, todos diferentes entre si.  A mediana do vetor é um elemento do vetor que seja maior que metade dos elementos do vetor e menor que (a outra) metade dos elementos.  Mais precisamente, a mediana de v[0..n-1] é um número m dotado de duas propriedades:  m é estritamente maior que exatamente ⌊(n-1)/2⌋ elementos do vetor e m é igual a algum elemento do vetor.  (Não confunda mediana com média. Por exemplo, a média de  1 2 99  é  51, enquanto a mediana é 2.)  Escreva um algoritmo que encontre a mediana de um vetor v[0..n-1] de números diferentes entre si.
  4. Escalonamento de tarefas.  Suponha que n tarefas devem ser processadas em um único processador.  Dadas as durações t1, … , tn das tarefas, em que ordem elas devem ser processadas para minimizar o tempo médio de conclusão de uma tarefa?

Estabilidade

Um algoritmo de ordenação é estável (= stable) se não altera a posição relativa dos elementos que têm o mesmo valor.  Digamos, por exemplo, que um vetor de números reais é ordenado com base na parte inteira dos números, ignorando a parte fracionária.  Se o algoritmo de ordenação for estável, os números que têm a mesma parte inteira continuarão na mesma ordem em que estavam originalmente:

original    44.0 55.1 55.2 66.0 77.0 22.9 11.0 22.5 33.0
ordenado    11.0 22.9 22.5 33.0 44.0 55.1 55.2 66.0 77.0

Eis outro exemplo. Digamos que cada elemento do vetor é um struct com dois campos: o primeiro contém o nome de uma pessoa e o segundo contém o ano de nascimento da pessoa. Suponha que o vetor original tem dois João da Silva, primeiro o que nasceu em 1990 e depois o que nasceu em 1995. Se o vetor for ordenado por um algoritmo estável com base no primeiro campo, os dois João da Silva continuarão na mesma ordem relativa: primeiro o de 1990 e depois o de 1995.

Exercícios 6

  1. O algoritmo de seleção é estável?
  2. O algoritmo de inserção é estável?
  3. Na função insercao, troque a comparação  v[i] > x  por  v[i] >= x.  A função modificada faz uma ordenação estável?