Advertisement
darkjessy94

Mergesort - l'arocca

Oct 17th, 2017
87
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.40 KB | None | 0 0
  1. #include <vector>
  2. #include <iostream>
  3.  
  4. using namespace std;
  5.  
  6.  
  7. void MergeSort(vector<int>& , int ,int);
  8. void Merge(vector<int> &, int, int, int);
  9.  
  10. int main()
  11. {
  12.     cout<<"Inserisci il numero degli elementi da ordinare: ";
  13.     int tot;
  14.     cin>>tot;
  15.     vector<int> arr1;
  16.     int x;
  17.     cout<<"Inserimento: "<<endl;
  18.     for(int i=0; i < tot ; i++){
  19.         cin>>x;
  20.         arr1.push_back(x);
  21.     }
  22.     MergeSort(arr1,0,arr1.size()-1);
  23.     cout<<"Vettore ordinato"<<endl;
  24.     for(auto z : arr1)
  25.         cout<<z<<" ";
  26.     return 0;
  27. }
  28.  
  29. void MergeSort(vector<int>& A, int s, int e)
  30. {
  31. if(s < e){
  32.      int m = (s + e)/2;
  33.      MergeSort(A, s, m);
  34.      MergeSort(A, m + 1, e);
  35.      Merge(A,s,m,e);
  36.     }
  37. }
  38.  
  39. void Merge(vector<int> &a, int l, int m, int r)
  40. {
  41.     int n1 = m-l+1, n2 = r - m;
  42.     vector<int> s(n1),d(n2);
  43.     for(int i = 0; i < n1; i++) //carica la metà sinistra del vettore a in l (l è lo spiazzamento che avviene nella ricorsione)
  44.         s.at(i) = a.at(l+i);
  45.     for(int j = 0; j < n2; j++) //carica la metà destra del vettore
  46.         d.at(j) = a.at(m+j+1);
  47.     int i=0, j=0 ,k;
  48.     s.push_back(0x7fffffff); //sentinelle che consentono l'inserimento
  49.     d.push_back(0x7fffffff); //anche dopo la fine di uno dei due array
  50.     for(k = l; k <= r; k++) //unione dei vettori in a in modo ordianto
  51.         (s.at(i)<=d.at(j)) ? a.at(k)=s.at(i++) : a.at(k)=d.at(j++);
  52. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement