Ordenação [Pt 2]: Mergesort e contando inversões

Para um vetor grande, não funciona um algoritmo O(n²). Precisamos de um melhor. Primeiro mostrarei a ideia e depois o tempo de execução.

Suponha que temos um vetor de tamanho N desordenado. Se ordenamos cada uma das metades separadamente, podemos juntar as metades em O(n = tamanho do vetor), certo? Explico melhor:

Temos as duas metades ordenadas. Para juntar elas, criamos um novo vetor. O menor elemento é ou o primeiro elemento da primeira metade ou o primeiro da segunda:

Ponto interessante. A gente também está fazendo inversões aqui. Quando colocamos o 1 na frente, o que fizemos na verdade foram sucessivas inversões:

Total de 4 inversões

Ou seja, fizemos 4 inversões, só que de um modo mais inteligente. Continuamos comparando, até acabarem os elementos:

Agora é só colocar os vetores da parte que sobrou, que já estão ordenados, no fim do vetor, e fim do algoritmo.

Então a ideia é ordenar a primeira parte, ordenar a segunda, e juntar para um vetor de 8 elementos. E o que é ordenar a primeira parte?

A primeira parte é um vetor de 4 elementos, e segue o mesmo esquema. Divide em duas partes, ordena a primeira, a segunda e junta. E essa nova primeira parte?

É um vetor de 2 elementos. Divide em duas partes (dois vetores de um elemento), ordena a primeira parte, a segunda e junta.

E o que é ordenar um vetor de um elemento? Não fazer nada.

Ou seja, definimos um algoritmo recursivo:

//Left eh onde comeca o vetor e right onde termina
void MergeSort(int * vet, int left, int right) {
    //Se soh tem um elemento, ou se o fim ta antes do começa
    //Acaba aqui mesmo
    if(left >= right) return;

    //Se nao, tem mais de um elemento
    int mid = (left+right)/2;
    //Ordena primeira parte
    MergeSort(vet, left, mid);
    
    //Ordena a segunda
    MergeSort(vet, mid+1, right);
    
    //Agora, a funcao que junta as partes
    Merge(vet, left, right);
    return;
}

E o tempo de execução é O(nlogn). O que consome tempo é juntar as duas partes, certo?

Fazemos esse procedimento de juntar as partes para cada nivel Log N vezes. Ou seja, o tempo de execução é N (já que somando as subpartes, totalizam N) * Log N.

A função que junta as partes é a seguinte:

//Funcao que divide o vetor em duas partes
//Assume que a primeira parte estah ordenada
//E que a segunda parte estah ordenada
//Mistura as duas e forma uma soh ordenada
void Merge(int * vet, int left, int right) {
    int aux_count = 0;
    //A posicao do meio no vetor
    int mid = (left+right)/2;

    //P1 e P2 sao os ponteiros que vao percorrer o vetor
    //P1 percorre a primeira metade (de left ate mid)
    //P2 percorre a segunda metade (de mid+1 ate right)
    int p1, p2;
    p1 = left;
    p2 = mid+1;

    //Enquanto nao percorreu nenhuma das metades inteira
    while(p1 <= mid && p2 <= right) {
        if(vet[p1] <= vet[p2]) //Se o da primeira metade eh menor
            aux[aux_count++] = vet[p1++];
  
        else //Se o da segunda metade eh menor
            aux[aux_count++] = vet[p2++];
    }
    //Ja percorreu uma metade inteira
    //Agora soh colocar os elementos da outra metade
    //Os elementos da outra metade jah estao ordenados entre si

    while(p1 <= mid)
        aux[aux_count++] = vet[p1++];

    while(p2 <= right)
        aux[aux_count++] = vet[p2++];
 
    //Copia os dados do vetor auxiliar pro vetor original
    for(int i = 0; i < aux_count; i++) {
        vet[left++] = aux[i];
    }
    return;
}

Com uma pequena alteração, podemos computar também o número de inversões, que ocorrem quando um elemento da segunda metade deve ficar na frente de um da primeira, mas isso fica como sugestão.

Problemas sugeridos:
URI 1088: Bolhas e baldes [link]
SPOJ BR (BALE11): Balé (problema da OBI) [link]

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