Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <stdio.h>
- #include <iostream>
- #include <string.h>
- #include <vector>
- #include <ctime>
- #include <cstdlib>
- #include <cmath>
- using namespace std;
- int N,contador=0;
- void Merge(vector<int> &ordenado,int inicio,int fin,int mitad)
- {
- int inicio_aux=inicio, mitad_aux=mitad;
- vector<int> aux;
- int grupob=mitad-inicio;
- while((mitad_aux!=fin+1 or inicio_aux!=mitad))
- if(inicio_aux!=mitad and ordenado[inicio_aux]<=ordenado[mitad_aux])
- {
- aux.push_back(ordenado[inicio_aux++]);
- grupob--;
- }
- else
- {
- if(mitad_aux!=fin+1)
- {
- aux.push_back(ordenado[mitad_aux++]);
- contador+=grupob;
- }
- else
- aux.push_back(ordenado[inicio_aux++]);
- }
- for (int i = inicio,j=0; j < aux.size(); ++i,j++)
- ordenado[i]=aux[j];
- }
- void MergeSort(vector<int> &ordenado,int inicio,int fin)
- {
- if(inicio>=fin)
- return;
- int mitad=(inicio+fin)/2;
- MergeSort(ordenado,inicio,mitad);
- MergeSort(ordenado,mitad+1,fin);
- Merge(ordenado,inicio,fin,mitad+1);
- }
- int main()
- {
- scanf("%d",&N);
- vector<int> ordenado(N);
- for (int i = 0; i < N; ++i)
- scanf("%d",&ordenado[i]);
- MergeSort(ordenado,0,ordenado.size()-1);
- cout<<endl<<"cantidad de combinaciones:"<<contador<<endl;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement