Я пытался сделать сортировку слиянием и сортировку вставкой и сравнить результат времени для них обоих. И от размера ввода массива от 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