Мой алгоритм сортировки слиянием занимает слишком много времени для ввода большого файла?
ну, это не совсем сортировка слиянием, алгоритм подсчитывает число инверсий в массиве, используя сортировку слиянием (в основном я просто добавил одну простую строку)
чтение и объединение 100 000 различных целых чисел из текстового файла занимает 2,415 секунды, в то время как другие, решившие ту же проблему (на coursera.com), сказали, что им понадобилось менее 0,5 секунды.
вот мой код, что пошло не так? чтение файла возможно? Спасибо
#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;
}
Решение
Одна проблема, которую я мог видеть, заключается в том, что в функции слияния вы выделяете слишком много места, и копирование обратно также занимает достаточно O (N), что делает общее время копирования O (N * N) вместо O (N * Log (N) )). Простое изменение функции слияния может выглядеть так:
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;
}
Другие решения
Других решений пока нет …
detector