У моего исходного вектора было {777, 7483, 3734, 6627, 7789, 8673}, и затем temp продолжил сортировку вектора, но я заметил через gdb, что моя temp копирует некоторые числа в вектор неправильно после пары шаг за шагом, у моего временного вектора были элементы {0, 3734, 7483, 3734, 6627, 0}. Итак, я знаю, что есть ошибка копирования, которая берет элемент v [] и дважды помещает его в temp. Я знаю, что алгоритм сортировки работает, потому что когда я распечатывал свой временный вектор, он сортировался, хотя элементы были не одинаковыми. Конечный вектор температуры имел {777, 3734, 3734, 3734, 3734, 7483}. Он выполняет сортировку, но просто имеет ошибку копирования, которую я не знаю, как исправить или как ее исправить
int
main (int argc, char* argv[])
{
size_t n = vectorSize();
vector<int> vect(n);
std::random_device sd;
std::mt19937 mt(sd());
std::uniform_int_distribution<int> dist (0, 9999);
for (size_t i = 0; i < n; ++i)
{
vect[i] = dist(mt);
}
mergeSort(vect);
cout << "Merge time: " << ms << endl;
//cout << "Merge compares: " << numCompares << endl;
vector<int> ACopy(vect);
std::sort(ACopy.begin(), ACopy.end());
if(vect == ACopy)
{
cout << "Merge ok? true" << endl;
}
else
{
cout << "Merge ok? false" << endl;
}
return EXIT_SUCCESS;
}
/************************************************************/
size_t
mergeSortH(vector<int>& v, vector<int>& temp, size_t first, size_t last)
{
if (last - first > 1)
{
size_t mid = first+(last-first) / 2;
mergeSortH(v, temp, first, mid);
mergeSortH(v, temp, mid, last);
outplaceMerge(v, temp, first, mid, last);
}
return 0;
}
/************************************************************/
size_t
outplaceMerge(vector<int>& v, vector<int>& temp, size_t first, size_t mid, size_t last)
{
size_t numCompares = 0;
size_t i1 = first;
size_t i2 = mid;
size_t i3 = first;
while((i1 < mid) && (i2 < last))
{
//check if first is less than mid
if(v[i1] < v[i2])
{
temp[i3] = v[i1];//swap
++i1;
++i3;
++numCompares;
}else{
temp[i3] = v[i2];//swap
++i2;
++i3;
++numCompares;
}
}
//while first half is less than mid
while(i1 <= mid)
{
temp[i3] = v[i1];
++i1;
++i3;
++numCompares;
}
//while second half is less than last
while(i2 <= last)
{
temp[i3] = v[i2];
++i3;
++i2;
++numCompares;
}
//copy elements back into original vector
for(i1 = first; i1 < i3; ++i1)
{
v[i1] = temp[i1];
}
cout << temp[i3] << endl;
return numCompares;
}
/************************************************************/
size_t
mergeSort(vector<int>& v)
{
vector<int> temp(v.size());
return mergeSortH(v, temp, 0, v.size());
}
Вектор temp должен взять все элементы из вектора orignal и отсортировать их по вектору temp. Затем, когда временный вектор отсортирован, он копирует все элементы по порядку из временного вектора. Исходный вектор = {777, 7483, 3734, 6627, 7789, 8673}, затем сортируйте и объединяйте в temp, так что temp должен равняться {777, 3734, 6627, 7483, 7789, 8673}, а затем эти элементы должны быть помещены обратно в v [ ]. Стандартная сортировка (которая всегда будет сортироваться) должна равняться вектору сортировки слиянием, и тогда она имеет оператор cout, который говорит true или false, если vector = Acopy.