Question

Buna, cum se poate realiza recursiv o sortare prin interclasare in c++?

Stiu sa interclasez doi vectori insa cum se poate si sorta si interclasa in acelas timp recursiv?
Împarți șirul pe care îl ai de sortat în 2 jumătăți
Sortezi jumătatea din stânga, aplicând aceeași metodă de sortare
Sortezi jumătatea din dreapta, aplicând aceeași metodă de sortare
La final, interclasezi cele 2 șiruri sortate
Am gasit ceva de genul insa nu prea inteleg cum le as putea sorta recursiv.

Answer 1

Răspuns:

#include <iostream>

using namespace std;

void merge(int arr[], int l, int m, int r)

{

   int i, j, k;

   int n1 = m - l + 1;  //numarul de elemente din stanga

   int n2 =  r - m;  // numarul de elemnte din dreapta

 

   int L[n1], R[n2]; //array pentru partea stanga si pentru partea dreapta

 

   //copiem arr in cei 2 vectori

   for (i = 0; i < n1; i++)

       L[i] = arr[l + i];

   for (j = 0; j < n2; j++)

       R[j] = arr[m + 1+ j];

 

   i = 0;  

   j = 0;  

   k = l;

   

   //Incepem interclasarea

   while (i < n1 && j < n2)

   {

       if (L[i] <= R[j])

       {

           arr[k] = L[i];

           i++;

       }

       else

       {

           arr[k] = R[j];

           j++;

       }

       k++;

   }

 

  //in caz ca unul din L sau R s-au terminat, copiem ce mai ramane daca exista

  //Pentru L

   while (i < n1)

   {

       arr[k] = L[i];

       i++;

       k++;

   }

 

 //Pentru R

   while (j < n2)

   {

       arr[k] = R[j];

       j++;

       k++;

   }

}

 

void mergeSort(int arr[], int l, int r)

{

   if (l < r)

   {

       //aflam mijlocul

       int m = l+(r-l)/2;  // merge si (l+r)/2 , dar celalalt evita overflow

 

       //impartim array-ul recursiv in jumatati pana cand partea din stanga va fi mai mare decat partea din dreapta  

       mergeSort(arr, l, m);

       mergeSort(arr, m+1, r);

       //aici se va ajunge ultima data,asta insemnand ca va sorta de la cat mai putine elemente la cat mai mult

       

       merge(arr, l, m, r);

   }

}

 

int main()

{

   int arr[6] = {22,13,17,5, 11,1};

   int n = 6;

   mergeSort(arr, 0, n - 1);

   

   for(int i = 0 ; i < n ;i++){

       cout<<arr[i]<<" ";

   }

   return 0;

}

Explicație: