Merge Sort Divide et Impera

Divide et Impera - Merge Sort

Algoritmii Divide et Impera:

• impart problema in subprobleme asemanatoare cu cea initiala, mai mici ca dimensiune pe care apoi le rezolva recusiv si apoi combina solutiile pentru a crea o solutie pentru problema originala;
• 3 pasi:
  • Divide: problema data este divizata intr-un set de subprobleme;
  • Impera: subproblemele sunt rezolvate recursiv (daca sunt suficient de mici, sunt rezolvate direct);
  • Combina: solutiile problemelor sunt combinate pentru a obtine solutia problemei initiale;
• Avantaje: algoritmi eficienti; faciliteaza paralelizarea algoritmului;
• Dezavantaje: overheaddatorat recusivitatii.

Merge Sort

1.Divide: divide cele n elemente ce trebuie sortate in n/2, pana se ajunge la submultimi de UN element -care sunt deja sortate.
2.Impera: sorteaza recursiv secventele folosind Merge Sort.
3.Combina: se asambleaza solutiile initiale.

Lucrurile vor evolua cam asa:


Sursa Imaginii: Wikipedia

Si acum, codul meu...



Codul (in C):

// Mergesort in C
  #include<stdio.h>
  #include<stdlib.h>

#define INF 3200

int p=1; int r=7;
int A[100];


int initialize_vector(int A[]){
A[1]=10 ;A[2]=1 ;A[3]=17 ;A[4]=0 ;A[5]=2 ;A[6]=1 ;A[7]=0 ;
}

int MERGE_eu(int A[],int p, int q, int r){
 int n1, n2; //n1 = nr elem din stanga, n2 = nr elem din dreapta
 n1 = q-p+1;
 n2 = r-q;
//S[] = vector elem stanga, D[] = vector elem dreapta - alocare dinamica
 int *S, *D;
 S = (int *)calloc(n1+1, sizeof(int));
 D = (int *)calloc(n2+1, sizeof(int));
//acum initializam vectorii, S preia valorile din A-ul stang, D din A-ul drept
 int i, j;
 for(i=1; i<=n1; i++)
  S[i]=A[p+i-1];
 for(j=1; j<=n2; j++)
  D[j]=A[q+j];
 
 S[n1+1]=INF; D[n2+1]=INF;
 i=1; j=1;
 
 int k;
 for(k=p; k<=r; k++)
  if(S[i]<=D[j]){
   A[k]=S[i]; i=i+1;}
  
  else {
   A[k]=D[j]; j=j+1; } 
}

int MERGE_SORT_eu(int A[], int p, int r){
     if(p<r){ //daca p>=r, inseamna ca vectorul are maxim 1 element -e sortat deja
 int q = (p+r)/2; //mijlocul vectorului
 MERGE_SORT_eu(A, p, q); //stanga
 MERGE_SORT_eu(A, q+1, r); //dreapta
 MERGE_eu(A, p, q, r); //combinarea subsecventelor
 }

}

int main(){
 printf("test\n");
 initialize_vector(A);
 MERGE_SORT_eu(A,p,r);
int i;
for(i=p; i<=r; i++)
 printf("%d ", A[i]);
printf("\n");

return 0;
}

Surse:

• Wikipedia - Merge Sort Divide and Conquer
• Cormen - Introducere in Algoritmi
• Cursul de Proiectarea Algoritmilor