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.)
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.
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].
exch(a[i], a[min])por
if (i != min) exch(a[i], a[min])?
void exch (Item A, Item B) {
Item t = A; A = B; B = t;
}
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.
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
}
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].
a[j] = vpor
if (j < i) a[j] = v?
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; } }
#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]);
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.
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.
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.
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)
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.
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.
typedef struct node* link;
struct node {
int chave;
link next;
};
typedef struct node* link;
struct node {int chave; link next;};