Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <vector>
- #include <iostream>
- using namespace std;
- void MergeSort(vector<int>& , int ,int);
- void Merge(vector<int> &, int, int, int);
- int main()
- {
- cout<<"Inserisci il numero degli elementi da ordinare: ";
- int tot;
- cin>>tot;
- vector<int> arr1;
- int x;
- cout<<"Inserimento: "<<endl;
- for(int i=0; i < tot ; i++){
- cin>>x;
- arr1.push_back(x);
- }
- MergeSort(arr1,0,arr1.size()-1);
- cout<<"Vettore ordinato"<<endl;
- for(auto z : arr1)
- cout<<z<<" ";
- return 0;
- }
- void MergeSort(vector<int>& A, int s, int e)
- {
- if(s < e){
- int m = (s + e)/2;
- MergeSort(A, s, m);
- MergeSort(A, m + 1, e);
- Merge(A,s,m,e);
- }
- }
- void Merge(vector<int> &a, int l, int m, int r)
- {
- int n1 = m-l+1, n2 = r - m;
- vector<int> s(n1),d(n2);
- for(int i = 0; i < n1; i++) //carica la metà sinistra del vettore a in l (l è lo spiazzamento che avviene nella ricorsione)
- s.at(i) = a.at(l+i);
- for(int j = 0; j < n2; j++) //carica la metà destra del vettore
- d.at(j) = a.at(m+j+1);
- int i=0, j=0 ,k;
- s.push_back(0x7fffffff); //sentinelle che consentono l'inserimento
- d.push_back(0x7fffffff); //anche dopo la fine di uno dei due array
- for(k = l; k <= r; k++) //unione dei vettori in a in modo ordianto
- (s.at(i)<=d.at(j)) ? a.at(k)=s.at(i++) : a.at(k)=d.at(j++);
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement