Ordenação: algoritmos elementares

Este capítulo é um resumo de parte do capítulo 6 (Elementary Sorting Methods) do livro do Sedgewick. Esse material também aparece nas seções 7.1 e 7.2 do livro do Roberts.  O capítulo trata do seguinte

Problema da ordenação:  Rearranjar um vetor  a[p..r]  de modo que ele fique em ordem crescente.

Um vetor  a[p..r]  está em ordem crescente se  a[p] a[p+1] ... a[r].  (A propósito, se a[p] < a[p+1] < ... < a[r],  dizemos que o vetor está em ordem estritamente crescente.)

Convenções

De que tipo é o vetor a[p..r] que queremos ordenar?  Os elementos do vetor podem ser de qualquer tipo que admita comparações.  Em particular, os elementos podem ser do tipo int, ou do tipo float, ou double, ou char, ou char*, etc.  Adotaremos a convenção de que os elementos o vetor são do tipo fictício  Item  e usaremos um typedef para escolher um tipo concreto. Podemos dizer, por exemplo,

typedef float Item;

Este capítulo e os próximos três estudam vários algoritmos para o problema da ordenação. Todos os algoritmos que estudaremos envolvem duas operações básicas: uma para comparar dois elementos do vetor e uma para intercambiar (= exchange) dois elementos. Para destacar essas operações, vamos representá-las pelas macro-instruções

#define less(A, B) (A < B)
#define exch(A, B) {Item t = A; A = B; B = t;}

que serã aplicadas a objetos A e B do tipo Item.

Exercício

  1. [Sedg 6.52]  Escreva uma função que verifique se um vetor a[p..r] de Items está em ordem crescente. Quantas comparações entre elementos do vetor sua função executa?

Algoritmo de Seleção

A seguinte função (inspirada no programa 6.2 de Sedgewick) implementa o algoritmo de seleção para o problema da ordenação. O código usa duas macro-instruções: uma para comparar dois elementos do vetor e uma para intercambiar (= exchange) dois elementos.

#define less(A, B) (A < B)
#define exch(A, B) {Item t = A; A = B; B = t;}

// A função recebe um vetor de a[p..r] de
// Items e rearranja o vetor em ordem
// crescente.

void selection (Item a[], int p, int r) {   
   int i, j;
   for (i = p; i < r; i++) { 
      int min = i;
      for (j = i+1; j <= r; j++) 
         if (less(a[j], a[min]) min = j;
      exch(a[i], a[min]);
   } 
}

Eis as invariantes que provam a correção da função: no início de cada repetição do for externo (controlado por i),

p         i         r
110 120 120 130 140 666 999 140 999 666 999
pequenos, crescente grandes

Note que o algoritmo funciona corretamente até mesmo em casos extremos:  quando p == r, quando p == r+1 e quando a[p] == a[p+1] == ... == a[r].

Exercícios

  1. Na função selection, que acontece se trocarmos  exch(a[i], a[min])  por  if (i != min) exch(a[i], a[min])?
  2. Na função selection, que acontece se trocarmos a macro  exch  pela função abaixo?
    void exch (Item A, Item B) {
       Item t = A; A = B; B = t;
    }
    
  3. Aplique a função selection ao seguinte vetor a[1..8]:

    88  99  33  99  44  77  99  11

    Diga qual a sequência de pares (i,j) para os quais a[i] é comparado com a[j] durante a execução da função.

  4. Escreva uma versão recursiva do algoritmo de seleção. 
  5. [Seção 6.8, Sedgewick]  Suponha que cada Item é uma cadeias de caracteres (= string). Modifique os #define e acrescente um typedef de modo que a função selection se aplique a esse caso.

Teste

O programa abaixo (adaptado do programa 6.1 do livro de Sedgewick) pode ser usado para testar a função selection. O programa consiste em ordenar um vetor de números inteiros e exibir o resultado. O primeiro argumento na linha de comando é o número máximo, digamos N, de elementos do vetor a ser ordenado. O segundo argumento é 1 ou 0: se for 1 então o vetor é gerado aleatoriamente; se for 0 então o programa espera que o usuário forneça N (ou menos) números inteiros.

#include <stdio.h>
#include <stdlib.h>

typedef int Item; 
#define less(A, B) (A < B)
#define exch(A,B) {Item t = A; A = B; B = t;} 

int main (int argc, char* argv[]) { 
   int i, N, sw;
   N = atoi(argv[1]);
   sw = atoi(argv[2]);
   int* a;
   a = malloc(N * sizeof (int));
   if (sw) 
      for (i = 0; i < N; i++) {
         float r1 = rand();
         float r2 = RAND_MAX + 1.0;
         a[i] = (r1/r2) * N; 
         // int aleatório em 0..N-1
      }
   else { 
      for (i = 0; i < N; i++) 
         if (scanf("%d", &a[N]) != 1) break;
      N = i;
   }
   selection (a, 0, N-1);
   for (i = 0; i < N; i++) 
      printf("%3d ", a[i]);
   printf("\n");
   free(a);
   return 0; // sucesso
}

Algoritmo de Inserção

Considere agora um segundo algoritmo para o problema da ordenação: o algoritmo de inserção. A seguinte função (adaptada do programa 6.3 de Sedgewick) implementa o algorimo.

#define less(A, B) (A < B)

// A função recebe um vetor de a[p..r] de
// Items e rearranja o vetor em ordem
// crescente.

void insertion (Item a[], int p, int r) { 
   int i;
   for (i = p+1; i <= r; i++) { 
      int j = i; 
      Item v = a[i]; 
      while (p < j && less(v, a[j-1])) { 
         a[j] = a[j-1]; 
         j--; 
      }
      a[j] = v; 
   } 
}

Eis a invariante que prova a correção da função: no início de cada repetição do for, o vetor  a[p..i-1]  está em ordem crescente.

p crescente   i         r
444 555 555 666 777 222 999 222 999 222 999

Note que o algoritmo funciona corretamente até mesmo em casos extremos:  quando p == r, quando p == r+1 e quando a[p] == a[p+1] == ... == a[r].

Exercícios

  1. Na função insertion, que acontece se trocarmos  a[j] = v  por  if (j < i) a[j] = v?
  2. Discuta a seguinte versão da função insertion:
    void insertion2 (Item a[], int p, int r) {
       for (int i = p+1; i <= r; i++) {
          int j = i;
          while (p <= j-1 && less(a[j], a[j-1])) {
             exch(a[j], a[j-1]);
             j--;
          }
          a[j] = v; } }
    
  3. Discuta a seguinte maneira de implementar a ordenação por inserção:
    #define compexch(A,B) if (less(B,A)) exch(A,B)
    
    void insertion (Item a[], int p, int r) { 
      int i;                     // 1
      for (i = r; i > p; i--)    // 2
         compexch(a[i-1], a[i]); // 3
      for (i = p+2; i <= r; i++) { 
         int j = i; 
         Item v = a[i]; 
         while (less(v, a[j-1]) { 
            a[j] = a[j-1]; 
            j--; 
         }
         a[j] = v; 
       } 
    }
    
    Qual o efeito de trocar as linhas 2 e 3 pelas linhas a seguir?
    for (i = p+1; i <= r; i++) 
       compexch(a[p], a[i]);
    
  4. Aplique a função insertion ao seguinte vetor a[1..8]:

    88  99  33  99  44  77  99  11

    Diga qual a sequência de pares (i,j) para os quais a[i] é comparado com a[j] durante a execução da função.

  5. Escreva uma versão recursiva do algoritmo de inserção. 
  6. Escreva uma função que rearranje um vetor a[p..r] de modo que ele fique em ordem decrescente. Sua função deve ser uma adaptação de insertion. Escreva duas versões de sua função: uma iterativa e uma recursiva.

 


Consumo de tempo do algoritmo de seleção

O consumo de tempo da função selection é proporcional ao número de comparações (comando less(a[j],a[min]) pois o tempo que decorre entre duas comparações consecutivas não depende do tamanho do vetor. Digamos que N é o número de elementos do vetor a[p..r], ou seja,

N = r-p+1.

A função jamais executa mais que (N-1)×(N-1) comparações.  Mais precisamente, o número de comparações no pior caso é  (N-1) + (N-2) + ... + 3 + 2 + 1  =  N(N-1)/2 . Esse número é um pouco menor que

N2/2

e portanto essencialmente igual ao número de pares de elementos de um conjunto com N elementos. Conclusão: o algoritmo essencialmente compara cada elemento do vetor com cada um dos demais.

É interessante contar o número de movimentações, ou seja, o número de vezes que selection copia um elemento do vetor de um lugar para outro (comando exch(a[i],a[min])). Esse número é apenas N, mesmo no pior caso. Como se vê, o consumo total de tempo do algoritmo não é proporcional ao número de movimentações.

Consumo de tempo do algoritmo de inserção

A execução da função insertion consome tempo proporcional ao número de comparações (comando less(v,a[j-1]) entre elementos do vetor. Sedgewick mostra (seção 6.5) que, mesmo no pior caso, esse número não passa de

N2/2 .

O número de movimentações (comando a[j] = a[j-1]) também é aproximadamente  N2/2.

Exercícios

  1. [Sedg 6.26]  Aplique as funções selection e insertion a um vetor a[p..r] cujos elementos são todos iguais. Qual das duas funções é mais rápida? Repita o exercício supondo que o vetor é crescente.
  2. Suponha que a[1..n] é um vetor de números inteiros e que você tem um índice k tal que  a[1..k] < 100  e  a[k+1..n] > 100.  Se quero rearranjar o vetor em ordem crescente, qual das alternativas é mais rápida:

 


Ordenação de vetores de structs

Em muitas aplicações, os objetos do tipo Item — e portanto os elementos do vetor a[p..r] — são structs e a ordem crescente desejada é relativa a um dos campos do struct. Chamaremos esse campo de chave (= key).  Veja um exemplo:

struct registro {
   int   chave;
   float campo1;
   int   campo2;
   char* campo3;
};

typedef struct registro Item;

Para rearranjar um tal vetor em ordem lexicográfica basta alterar a definição de less como segue:

#define less(A, B) (A.chave < B.chave)

Se os structs são volumosos, cada execução da macro exch consome muito tempo. Para evitar isso, é melhor que os objetos do tipo Item — e portanto os elementos do vetor a[p..r] — seja ponteiros para os structs. Por exemplo, podemos ter

typedef struct registro* Item;
#define less(A, B) (A->chave < B->chave)

Estabilidade

Dizemos que um algoritmo de ordenação é estável se não muda a ordem relativa dos elementos que têm uma mesma chave. Por exemplo, se o algoritmo transforma um vetor como

881  99  882  883  77

em   77  882  881  883  99   então o algoritmo não é estável. (Esse exemplo mostra apenas as chaves dos elementos do vetor e usa os subscritos para representar os demais campos.)

Imagine, por exemplo, que cada elemento do vetor contém o nome e o número de identificação de um aluno. Suponha que o vetor já está em ordem crescente de números. Se usarmos um algoritmo estável para rearranjar o vetor em ordem lexicográfica de nomes, cada grupo de homônimos (alunos com o mesmo nome) continuará em ordem crescente de número de identificação.

Exercícios

  1. Suponha que cada elemento do vetor a[p..r] é do tipo
    struct record { 
       char  nomedoaluno[50]; 
       float nota; 
    };
    
    Parte 1: Defina o tipo Item e modifique os #define de modo que a função selection rearranje o vetor em ordem crescente dos campos nota.  Parte 2: Repita o exercício de modo que a função insertion rearranje o vetor em ordem lexicográfica dos campos nomedoaluno.
  2. [Sedg 6.14]  O algoritmo de ordenação por seleção é estável?  O algoritmo de ordenação por inserção é estável?
  3. [Sedg 6.18]  Suponha que alteramos a definição de less(A,B) para (A <= B). Essa variante da função insertion é estável?

 


Mais exercícios

  1. Escreva uma função que ordene uma lista encadeada. Suponha que a chave de cada nó da lista é um número inteiro. Imite a função selection.
    typedef struct node* link;
    struct node {
       int  chave; 
       link next;
    };
    
  2. Escreva uma função que ordene uma lista encadeada. A chave de cada nó da lista é um inteiro. Imite a função insertion.
    typedef struct node* link;
    struct node {int chave; link next;};
    

 


Veja minhas notas de aula sobre algoritmos elementares de ordenação.
URL: www.ime.usp.br/~pf/mac0122-2002/
Atualizado em 2018-01-01
© Paulo Feofiloff
IME-USP