Ordenação [Pt 1]: Bubblesort e contando inversões

Ordenar um vetor é um problema famoso e que possui muitas soluções, algumas intuitivas ou não. Vamos começar com o pior método de ordenar, contextualizando:

Suponha que estamos em uma corrida de fórmula 1. Cada competidor começa em uma posição arbitrária, e termina em outra posição arbitrária.

Os carros se ordenam quando um passa de outro. Por exemplo:

O que fizemos foi que vimos todos os pares de carros e trocamos alguns de posição. Observe que no fim, o último carro está na posição certa.

Se na segunda volta fazemos o mesmo:

Agora o carro 4 está na posição certa (não precisa checar o par (4,5), já que o 5 já está na posição certa). Na terceira volta:

Agora o carro 3 está na posição certa (não é necessário checar os pares (3,4) e (4,5)).

Essa é a ideia do Bubblesort. Percorremos o vetor N-1 vezes, checando o vetor até o fim, mas a cada iteração reduzimos o "fim" em 1. Para cada par de pontos, vemos se é possível trocar ou não.

//BubbleSort
int N;
int vet[100];

for(int i = 0; i < N; i++) {
    for(int j = 0; j < i-1; j++) {
        if(vet[j] > vet[j+1]) {
            //Variavel auxiliar para troca
            int aux = vet[j];
            vet[j] = vet[j+1];
            vet[j+1] = aux;
        }
    }
}

O tempo de execução é (N + N-1 + N-2 + ... + 1) = O(n²), ineficiente para vetores grandes (acima de 10³).

Problema sugerido:
URI 1228: Grid de Largada [link]

Continuar para parte 2 [link].
Códigos no github [link].