![[Insertion_Sort_Animation.gif]](img/Insertion_Sort_Animation.gif "Copiado de https://commons.wikimedia.org/wiki/File:Insertion_Sort_Animation.gif")
![[Selection-sort-github-slower.gif]](img/Selection-sort-github-slower.gif "Copiado de https://github.com/SimonWaldherr/GolangSortingVisualization")
Primeiro, coloque os números em ordem crescente.
Depois decidiremos 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 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.
int verifica (int v[], int n) {
if (n > 1)
for (int i = 1; i < n; i++)
if (v[i-1] > v[i]) return 0;
return 1; }
int verifica (int v[], int n) {
int sim;
for (int i = 1; i < n; i++)
if (v[i-1] <= v[i]) sim = 1;
else {
sim = 0;
break; }
return sim; }
O algoritmo de ordenação por inserção, ou algoritmo Insertionsort, é frequentemente usado para colocar em ordem um baralho de cartas (veja página aula da Khan Academy):
// Esta função rearranja o vetor v[0..n-1]
// em ordem crescente.
void
insertionsort (int n, int v[])
{
for (int j = 1; j < n; ++j) {
int x = v[j];
int i;
for (i = j-1; i >= 0 && v[i] > x; --i)
v[i+1] = v[i];
v[i+1] = x;
}
}
(Compare o for 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
j < n
,
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.
Quantas vezes a função insertionsort
compara x com um elemento do vetor?
Mais exatamente,
quantas vezes, no máximo, a função insertionsort
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 mesma linha da segunda coluna.
Portanto,
o número de execuções da comparação
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 insertionsort 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 tamanho 10N consumirá
100T segundos!
Essa análise mostra que
o algoritmo Insertionsort é lento demais
para ordenar vetores grandes.
Graças à sua simplicidade, entretanto,
o algoritmo é muito útil no caso de vetores pequenos.
Além disso,
no melhor caso
(por exemplo, se o vetor já está quase ordenados
),
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. A animação à direita (copiada da Wikimedia) mostra a ordenação por inserção de um vetor v[0..79] de números positivos. (Veja uma versão mais lenta da animação.) Cada elemento v[i] do vetor é representado pelo ponto de coordenadas (i, v[i]). Há várias outras animações interessantes na rede WWW:
v[i] > xpor
v[i] >= x. A nova função continua correta?
for (j = 1por
for (j = 0no código da função insertionsort? Que acontece se trocarmos
v[i+1] = xpor
v[i] = x?
for (int j = 1; j < n; ++j) {
int x = v[j];
for (int i = j-1; i >= 0 && v[i] > x; --i) {
v[i+1] = v[i];
v[i] = x; } }
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; } }
for (int j = 1; j < n; ++j) {
int x = v[j];
int i = j - 1;
while (i >= 0 && v[i] > x) {
v[i+1] = v[i];
--i; }
v[i+1] = x; }
Esta seção trata do algoritmo de ordenação por seleção, ou algoritmo Selectionsort. 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
selectionsort (int n, int v[])
{
for (int i = 0; i < n-1; ++i) {
int min = i;
for (int j = i+1; j < n; ++j)
if (v[j] < v[min]) min = j;
int 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 i < n-1
,
valem os seguintes invariantes:
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. Tal como o de ordenação por inserção, o algoritmo de ordenação por seleção faz cerca de n2/2 comparações entre elementos do vetor no pior caso.
Diferentemente do algoritmo Insertionsort, entretanto,
o algoritmo Selectionsort também faz cerca de n2/2
comparações no melhor caso
(por exemplo, quando o vetor já está quase ordenado
).
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 Insertionsort é preferível ao de seleção.
![[Selection-sort-github.gif]](img/Selection-sort-github.gif "Copiado de https://github.com/SimonWaldherr/GolangSortingVisualization")
Animações. A animação à direita (copiada da Wikipedia) mostra a ordenação por seleção de um vetor v[0..79] de números positivos. (A velocidade da animação não representa a velocidade do algoritmo. Veja uma versão mais lenta da animação.) Cada elemento v[i] do vetor é representado pelo ponto de coordenadas (i,v[i]). Há várias outras animações interessantes na rede WWW:
for (i = 0por
for (i = 1? Que acontece se trocarmos
for (i = 0; i < n-1por
for (i = 0; i < n?
v[j] < v[min]por
v[j] <= v[min]. A nova função continua correta?
struct registro {int aa; char *bb;};
(O campo aa pode ser o número de uma peça no estoque de uma loja e bb o nome da peça.) 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.
void insertionsort_al (int n, int v[]) {
for (int j = 1; j < n; ++j) {
int x = v[j];
int i;
for (i = j-1; i >= 0 ; --i) {
if (rand() > RAND_MAX/2)
v[i+1] = v[i];
else break; }
v[i+1] = x; } }
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).
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 como br-sem-acentos.txt que contém todas as palavras do português brasileiro com sinais diacríticos removidos. (O arquivo é grande; portanto, o seu programa deverá ser muito eficiente.)
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 do tipo double é ordenado considerando apenas a parte inteira dos números (e 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 relativa em que estavam originalmente. Na seguinte figura, a primeira linha mostra o vetor original e a segunda, o vetor ordenado por um algoritmo estável:
| 44.0 | 55.1 | 55.2 | 33.9 | 22.9 | 11.0 | 22.5 | 22.6 |
| 11.0 | 22.9 | 22.5 | 22.6 | 33.9 | 44.0 | 55.1 | 55.2 |
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 em que a pessoa nasceu.
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.
A estabilidade de um algoritmo de ordenação é uma propriedade útil que usaremos em outro capítulo.
v[i] > xpor
v[i] >= x. A função modificada faz uma ordenação estável?