Bubble sort (ordenação por transposição):

Varre o vetor diversas vezes, invertendo pares adjacentes fora de ordem.

void bubbleSort(int v[], int n) {
    int aux, mudou = 1, j = 0;

    while (mudou == 1) {
        mudou = 0;
        for (i = 2; i <= n - j; i++)
            if (v[i-1] > v[i]) {
                aux = v[i-1];
                v[i-1] = v[i];
                v[i] = aux;
                mudou = 1;
            }
        j++;
    }
}

Invariantes principais, no início de cada iteração:

a - o vetor é uma permutação do original,

b - v[n - j + 1 .. n] está ordenado,

c - v[n - j + 1] >= v[k], para 1 <= k <= n - j.

Prova por indução:

 - Base: invariantes valem trivialmente no início da primeira iteração.

 - H.I.: no início da j-ésima iteração o vetor é uma permutação do original, v[n - j + 1 .. n] está ordenado e v[n - j + 1] >= v[k], para 1 <= k <= n - j.

 - Passo: na j-ésima iteração o algoritmo percorre o vetor v[1 .. n - j] da esquerda para a direita trocando os pares adjacentes que estão invertidos. Com isso, o maior elemento deste vetor termina na posição n - j, já que ele sempre será trocado com o elemento a sua direita (invariante (c) vale no início da próxima iteração). Por H.I. o vetor v[n - j + 1 .. n] já está ordenado e o elemento na posição v[n - j] é menor ou igual a v[n - j + 1]. Portanto, v[n - j .. n] está ordenado (invariante (b) vale no início da próxima iteração). Como nenhum elemento foi removido ou duplicado, mas apenas permutado, invariante (a) continua válido.


Eficiência:

 - no melhor caso é O(n).

    - Por exemplo, vetor está ordenado ou tem apenas adjacentes fora de ordem.

    - O que acontece se trocarmos a condição "mudou == 1" por "j < n - 1"? Continua ordenando? Como fica o melhor caso?

 - no pior caso é O(n^2).

 - Por exemplo, vetor está ordenado exceto pelo menor estar na última posição, ou vetor está em ordem decrescente.


Ordenação é estável.

 - O que acontece se trocarmos "v[i-1] > v[i]" por "v[i-1] >= v[i]"? Continua ordenando? Continua estável? Sempre termina?


Ordenação é in place.

 - Só usa auxiliares de tamanho constante.


Animation: https://www.youtube.com/watch?v=JP5KkzdUEYI