Advertisement
Gustavo_Inzunza

Merge con count

Jun 10th, 2013
48
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.20 KB | None | 0 0
  1. #include <stdio.h>
  2. #include <iostream>
  3. #include <string.h>
  4. #include <vector>
  5. #include <ctime>
  6. #include <cstdlib>
  7. #include <cmath>
  8. using namespace std;
  9. int N,contador=0;
  10. void Merge(vector<int> &ordenado,int inicio,int fin,int mitad)
  11. {
  12.     int inicio_aux=inicio, mitad_aux=mitad;
  13.     vector<int> aux;
  14.     int grupob=mitad-inicio;
  15.     while((mitad_aux!=fin+1 or inicio_aux!=mitad))
  16.         if(inicio_aux!=mitad and ordenado[inicio_aux]<=ordenado[mitad_aux])
  17.         {
  18.             aux.push_back(ordenado[inicio_aux++]);
  19.             grupob--;
  20.         }
  21.         else
  22.         {
  23.             if(mitad_aux!=fin+1)
  24.             {
  25.                 aux.push_back(ordenado[mitad_aux++]);
  26.                 contador+=grupob;
  27.             }
  28.             else
  29.                 aux.push_back(ordenado[inicio_aux++]);
  30.         }
  31.     for (int i = inicio,j=0; j < aux.size(); ++i,j++)
  32.         ordenado[i]=aux[j];
  33. }
  34. void MergeSort(vector<int> &ordenado,int inicio,int fin)
  35. {
  36.     if(inicio>=fin)
  37.         return;
  38.     int mitad=(inicio+fin)/2;
  39.     MergeSort(ordenado,inicio,mitad);
  40.     MergeSort(ordenado,mitad+1,fin);
  41.     Merge(ordenado,inicio,fin,mitad+1);
  42. }
  43.  
  44. int main()
  45. {
  46.     scanf("%d",&N);
  47.     vector<int> ordenado(N);
  48.     for (int i = 0; i < N; ++i)
  49.         scanf("%d",&ordenado[i]);
  50.     MergeSort(ordenado,0,ordenado.size()-1);
  51.     cout<<endl<<"cantidad de combinaciones:"<<contador<<endl;
  52. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement