Metode de sortare – prin interclasare (Merge Sort)

Algoritmul de sortare prin inserţie este eficient pentru valori mici ale lui n (n<=i6). De aceea, sortarea prin interclasare propune o sortare bazată pe principiul Divide et Impera, care să utilizeze sortarea prin inserţie pentru valori mici ale lui n, rezultate prin descompunerea şirului iniţial în subşiruri. Algoritmul Merge Sort se bazează pe 3 paşi esenţiali: • separarea tabloului în 2 părţi de mărimi cât mai apropiate • sortarea acestor părţi prin apeluri recursive, până la atingerea unor valori mici ale lui n pentru care se aplică sortarea prin inserţie sau până la atingerea unor subşiruri de 1 element (cazul banal) • interclasarea părţilor sortate obţinându-se direct un şir ordonat crescător
#include “stdio.h”
#include “conio.h”
//funcţia care interclasează 2 şiruri ordonate crescător
void merge(int a[], int l, int m, int r)
{
  int b[100],i=l,j=m+1,k=l,ind;
  //atât timp cât nici unul din şiruri nu s-a terminat
  while((i <= m)&&(j <= r))   {     if(a[i] <= a[j])
      //dacă elementul din primul subşir e mai mic sau egal îl preluam
      //pe acesta în şirul interclasat
      b[k]=a[i++];
    else
      //dacă nu, preluăm din al doilea subşir
      b[k]=a[j++];
    k++; //k este indicele în şirul interclasat
  }
  if(i > m)
    //dacă primul subşir s-a terminat, preluăm restul elementelor din cel
    //de al doilea subşir
    for(ind=j;ind <= r;ind++,k++)     b[k]=a[ind];   else     //dacă al doilea subşir s-a terminat preluăm restul elementelor     //din primul subşir     for(ind=i;ind <= m;ind++,k++)     b[k]=a[ind];   //în final mutăm elementele interclasate în şirul original   for(ind=l;ind <= r;ind++)   a[ind]=b[ind]; } //funcţia recursivă de sortare prin interclasare void merge_sort(int a[], int 1, int r) {   int m;   //condiţia de oprire din reeursivitate   if(l < r)   {     //calculăm mediana pentru a permite împărţirea şirului în 2 subşiruri     m=(l+r)/2;     //aplicăm Divide et Impera pentru cele 2 subşiruri rezultate     merge_sort(a,l,m);     merge_sort(a,m+1,r);     //interclasăm subşirurile sortate     merge(a,l,m,r);   } } void main(void) {   int n,a[100],i;   printf("Introdu dim şirului:");   scanf("%d",&n);   printf("Introdu elem şirului:\n");   for(i=0;i < n;i++)   {     printf("a[%d]=",i);     scanf("%d",a+i);   }   merge_sort(a,0,n-1);   printf("Sirul sortat este:");   for(i=0;i < n;i++)     printf("%d ",a[i]);   putchar("\n");   getch(); }

Leave a Reply

Your email address will not be published. Required fields are marked *

4 × five =

Time limit is exhausted. Please reload CAPTCHA.