Algoritmo de Ordenação por Intercalação
UnB-\(\gamma\)

Discussão e implementação do Algoritmo linearítmico de Ordenação MergeSort.

Nesta aula foi discutido o algoritmo MergeSort, mas antes, iniciamos a discussão sobre o funcionamento da função intercala (merge) que é a base para o funcionamento do algoritmo de ordenação.

Na live foi implementada a intercalação que recebe dois ponteiros de vetores e seus respectivos intervalos fechados [l,r] (l para left [ou elemento mais a esquerda] e r para right [ou elemento mais a direita]) devolvendo um vetor alocado com os elementos dos dois vetores, a e b, intercalados. A função implementada em aula segue o conceito implementado abaixo:

 1: Item *intercala(Item *a, int la, int ra, Item *b, int lb, int rb)
 2: {
 3:   //Tamanhos dos vetores a e b
 4:   int ta=(ra-la+1);
 5:   int tb=(rb-lb+1);
 6: 
 7:   Item *c=malloc(sizeof(Item)*(ta+tb));
 8: 
 9:   //intervalos do vetor c
10:   int lc=0;
11:   int rc=(ta+tb-1);
12: 
13:   int ia=la, ib=lb,ic=lc;
14: 
15:   while(ia<=ra && ib<=rb)
16:   {
17:     if(lesseq(a[ia],b[ib]))
18:       c[ic++]=a[ia++];
19:     else
20:       c[ic++]=b[ib++];
21:   }
22:   while(ia<=ra)
23:     c[ic++]=a[ia++];
24:   while(ib<=rb)
25:     c[ic++]=b[ib++];
26:   return c;
27: }

Esta implementação difere, ligeiramente, da versão feita no vídeo indicado como MergeSort (no início da aula), que faz com que a função de intercalação receba um único vetor com os índices l,m,r (left,middle,right).

O efeito da intercalação é o mesmo, porém, a implementação feita em aula exige que o vetor c seja manipulado dentro do procedimento mergesort, diferentemente do outro vídeo.

A complexidade assintótica não é modificada e tão pouco agrega overhead adicional entre as versões. Fica interessante ter a manipulação diferente dos elementos para ter uma visão ampla da implementação.

Dessa forma o mergesort, em aula, foi implementado da seguinte forma:

28: void mergesort(Item *v,int l,int r)
29: {
30:   if(l>=r) return;
31:   int meio=(l+r)/2;
32:   mergesort(v,l,meio);
33:   mergesort(v,meio+1,r);
34:   //principal diferença do intercala não ser in-place
35:   Item *c=intercala(v,l,meio,v,meio+1,r);
36:   int t=r-l+1;
37:   for(int i=0;i<t;i++)
38:     v[l++]=c[i];
39:   free(c);
40: }

A principal diferença na mergesort acontece a partir da linha 35, onde o nosso procedimento manipula o vetor resultante da intercalação para dentro do vetor que está sendo ordenado.

Outra maneira de passar os parâmetros do vetor v como se fossem dois vetores realmente disjuntos, seria passando o ponteiro da posição inicial de cada left do vetor, substituindo a Linha 35 pela linha indicada abaixo:

1: Item *c=intercala(&v[l],0,meio-l,&v[meio+1],0,r-(meio+1));

O que acontece neste ponto é que passamos os ponteiros dos left de cada um dos vetores que devem ser intercalados, um deles começa em l e o outro em meio+1, o que precisamos calcular agora é qual seria o novo right de cada vetor, pois como cada vetor não começa no l do vetor original temos que recalcular o deslocamente de cada parte, ficando meio-l para a primeira metade e r-(meio+1) para a segunda metade.