Esta página trata do seguinte problema: Permutar (ou seja, rearranjar) os elementos de um vetor v[0..n-1] de tal modo que eles fiquem em ordem crescente, ou seja, de tal forma que tenhamos v[0] ≤ v[1] ≤ . . . ≤ v[n-1] .
Veja o verbete Sorting algorithm na Wikipedia.
Eis um algoritmo de ordenação muito popular. (Veja o verbete insertion sort na Wikipedia.) Ele é usado, por exemplo, 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 j, i, 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 em outra página.) 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,
o vetor v[0..j-1] está em ordem crescente.
Esta condição invariante é trivialmente verdadeira 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 |
Quanto tempo o algoritmo consome para fazer o serviço? O tempo é proporcional ao número de execuções da comparação "v[i] > x". Calculemos esse número. No pior caso, para cada valor de j, a variável i assume os valores j-1, . . . , 0.
| j | i | número de valores de i |
| 1 | 0 | 1 |
| 2 | 1, 0 | 2 |
| 3 | 2, 1, 0 | 3 |
| . . . | . . . . . . . | . . . |
| n-1 | n-2, n-3, . . . , 1, 0 | n-1 |
O número de execuções da comparação "v[i] > x" no pior caso é igual à soma da última coluna da tabela, ou seja,
n (n-1) / 2 .
Esse número cresce como n2. O algoritmo é um tanto lento: se a ordenação de n números leva t segundos então a ordenação de 2n números levará 4t segundos e a ordenação de 10n números consumirá 100t segundos!
Veja alguns applets de animação do algoritmo de inserção:
void ins (int n, int v[]) {
int j, i, 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;
}
}
}
void ins (int n, int v[]) {
int i, j, min, 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;
}
}
}
Eis outro algoritmo de ordenação muito popular. (Veja o verbete selection sort na Wikipedia.) Ele seleciona o menor elemento do vetor, depois o segundo 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 como e por que o algoritmo funciona basta observar que no início de cada repetição do for externo, imediatamente antes da comparação de j com n, valem as seguintes invariantes:
A tradução da segunda 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". As duas invariantes garantem que no início de cada iteração v[0], . . , v[i-1] já estão em suas posições definitivas.
| 0 | i-1 | i | n-1 | |||||||
| 110 | 120 | 120 | 130 | 140 | 666 | 999 | 666 | 999 | 666 | 999 |
| pequenos, crescente | grandes | |||||||||
Não é difícil verificar que o algoritmo de seleção, tal como o de inserção, faz cerca de n2/2 comparações entre elementos do vetor. Esse número cresce como n2.
Veja applets de animação do algoritmo de seleção:
void sel (int n, int v[]) {
int i, j, min, x;
for (i = 1; i < n; ++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;
}
}
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.
Um algoritmo de ordenação é estável (= stable) se não altera a posição relativa de elementos com mesmo valor. Por exemplo, se o vetor v[0..n-1] tiver dois elementos iguais a 222, primeiro um azul e depois um vermelho, um algoritmo de ordenação estável mantém o 222 azul antes do vermelho.
| original: | 444 | 555 | 555 | 666 | 777 | 333 | 999 | 222 | 111 | 222 | 888 |
| ordenado: | 111 | 222 | 222 | 333 | 444 | 555 | 555 | 666 | 777 | 888 | 999 |
Eis um exemplo melhor. 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 1950 e depois o que nasceu em 1970. 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 1950 e depois o de 1970.
Invente um algoritmo de ordenação que seja mais rápido que o de inserção e o de seleção.