Mein merge sort-Algorithmus dauert zu lange für die Eingabe großer Dateien?

Question

Nun, es ist nicht genau eine Merge-Sortierung, der Algorithmus zählt die Anzahl auf Inversionen in einem Array mit merge sort (im Grunde habe ich nur eine einfache Zeile hinzugefügt) dauert 2.415 Sekunden zum Lesen und Zusammenführen 100000 verschiedene ganze Zahlen aus einer Textdatei zu sortieren andere, die das gleiche Problem gelöst haben (auf courstra.com), sagten, dass sie weniger als 0,5 Sekunden brauchten

hier ist mein Code, was ist schiefgelaufen? Datei lesen vielleicht?

dank

#include <bits/stdc++.h> 

using namespace std; 
int a,b,i,j,n,x,k; 
int t[100000]={0}; 
long long int s=0; 

void merge(int a, int mid, int b) 
    { 
     i=a; 
     j=mid+1; 
     k=a; 
     int v[100000]={0}; 
     while(i<=mid && j<= b) 
     { 
      if (t[i]<t[j]) 
       {v[k]=t[i]; 
       i++; 
       } 
      else 
      {v[k]=t[j]; 
      j++; 
       s+=mid-i+1; //this line here counts the inversions 
      } 
      k++; 
     } 
     while(i<=mid) 
     {v[k]=t[i]; 
     i++; k++;} 

     while(j<=b) 
     {v[k]=t[j]; 
     j++; k++;} 

     for (i=a;i<k;i++) 
     t[i]=v[i]; 
    } 


void mergeSort(int a, int b) 
    { 
     if(a<b) 
     { 
      int mid=(a+b)/2; 
      mergeSort(a,mid); 
      mergeSort(mid+1,b); 
      merge(a,mid,b); 
     } 
    } 


int main(){ 
    ifstream fin("C:\\Users\\ASUS\\Desktop\\coursera.txt"); 
    n=100000; 
    for(i=0;i<n;i++) 
     fin>>t[i]; 

    mergeSort(0,n-1); 

    cout<<endl<<s; 

} 

Answer 1

Eine Frage, die ich sehen konnte, ist, dass in Merge-Funktion, Sie zu viel Speicherplatz zuweisen, und die Kopie zurück nehmen auch ganz O (N), die die Gesamtkopierzeit O (N * N) anstelle machen von O (N * Log (N)). Eine einfache Änderung in der Zusammenführungsfunktion könnte wie folgt aussehen:

void merge(int a, int mid, int b) 
{ 
    i = a; 
    j = mid + 1; 
    k = 0; 
    int* v = new int[b - a + 1]; 
    while (i <= mid && j <= b) 
    { 
     if (t[i]<t[j]) 
     { 
      v[k] = t[i]; 
      i++; 
     } 
     else 
     { 
      v[k] = t[j]; 
      j++; 
      s += mid - i + 1; //this line here counts the inversions 
     } 
     k++; 
    } 
    while (i <= mid) 
    { 
     v[k] = t[i]; 
     i++; k++; 
    } 

    while (j <= b) 
    { 
     v[k] = t[j]; 
     j++; k++; 
    } 

    for (i = 0; i<k; i++) 
     t[a+i] = v[i]; 

    delete[] v; 
    v = NULL; 
}