Опитвам се да направя сортиране чрез сливане и сортиране при вмъкване и сравнявам резултата от времето и за двете. И от входен размер на масив 10 до 10000 сортирането чрез сливане е по-бавно от сортирането чрез вмъкване
това е кодът за сортиране на вмъкване
vector<int> insertion_sort(vector<int> vec)
{
for(int i = 1 ; i <vec.size();i++)
{
int j = i-1;
while(j>=0 && vec[j+1]<vec[j] )
{
int x = vec[j+1];
vec[j+1] = vec[j];
vec[j--] = x;
}
}
return vec;
}
И това е кодът за сортиране на сливане
vector<int> merge(vector<int> left,vector<int> right)
{
int i = 0;
int j = 0;
vector<int> ret(left.size()+right.size());
int it = 0;
for(; i <left.size() && j<right.size();)
{
if(left[i]<right[j])
ret[it++]=(left[i++]);
else if(right[j]<left[i])
ret[it++]=(right[j++]);
else ret[it++]=(left[i++]),ret[it++]=(right[j++]);
}
for(;i<left.size();)
ret[it++]=(left[i++]);
for(;j<right.size();)
ret[it++]=(right[j++]);
return ret;
}
vector<int> merge_sort(vector<int> A,int start,int end)
{
if(start >= end)
{
vector<int> v(1);
v[0]=(A[start]);
return v;
}
int mid = (start+end )/ 2;
vector<int> left = merge_sort(A,start,mid);
vector<int> right = merge_sort(A,mid+1,end);
return merge(left,right);
}
и накрая така ги извиквам всички и изчислявам времето
int main()
{
vector<int> rand_vec;
srand(time(0));
for(int i = 0 ; i <SIZE;i++)
{
rand_vec.push_back(rand()%SIZE);
}
int t = clock();
vector<int> merge_sorted = merge_sort(rand_vec,0,rand_vec.size()-1);
puts("");
printf("merge sort time = %d\n",clock() - t );
t = clock();
vector<int> insertion_sorted = insertion_sort(rand_vec);
puts("");
printf("insertion sort time = %d\n",clock() - t );
return 0;
}
Искам да знам дали съм направил нещо нередно в този код, за да направя времето за сортиране чрез сливане повече от времето, използвано за сортиране чрез вмъкване.
Благодаря.
vector<int>
, използвайте*vector<int>
(и съответно променете останалата част от кода). - person SJuan76   schedule 12.10.2013vector<int>&
;) - person lolando   schedule 12.10.2013reserve
за вашия вектор, преди да използвате хилядиpush_back
, когато знаете размера предварително - person lolando   schedule 12.10.2013reserve
, а неreverse
. Посочете крайния размер, така че векторът да не расте на всеки няколко входа. - person SJuan76   schedule 12.10.2013reserve
задава капацитета, а не размера - person lolando   schedule 12.10.2013