Векторы MergeSort с использованием векторных итераторов

Мне нужно реализовать MergeSort для сортировки вектора целых чисел с использованием векторных итераторов.
Я реализовал это, но я получаю эту ошибку: векторный итератор не разыменовывается.

В качестве параметров для функции слияния я использую (A.begin (), A.end ()) где A — мой вектор, который содержит
n элементов.

#include <iostream>
#include <vector>

using namespace std;

void swap(vector<int>::iterator first,vector<int>::iterator last)
{
int temp;
temp=*first;
*first=*last;
*last=temp;
return;
}void mergesort(vector<int>::iterator first,vector<int>::iterator last)
{
if(first==last) return;
if(first+1==last)
{
if(*last>*first) swap(first,last);
return;
}

vector<int>::iterator middle;
middle=first+(last-first)/2;

mergesort(first,middle);
mergesort(middle+1,last);

int a,b,pa,pb;
vector<int> h;
//the number of elements in a
pa=middle-first+1;
//the number of elements in b
pb=last-middle;
h.resize(pa+pb);
a=0; b=0;

while(a<pa && b<pb)
if(*(first+a)<*(middle+1+b))
{
h[a+b]=*(first+a); a++;
}
else
{
h[a+b]=*(middle+1+b); b++;
}

while(a<pa)
{
h[a+b]=*(first+a); a++;
}
while(b<pb)
{
h[a+b]=*(middle+1+b); b++;
}

for(int i=0;i<((a+b)-1);i++)
*(first+i)=h[i];

return;
}int main(){

vector<int>A;

for(int i=1000;i>0;i--)
{
A.push_back(i);
//vector of integer: 1000,999,998 ... 3,2,1
}

mergesort(A.begin(),A.end());
//sort vector elements from smallest to biggest: 1,2,3...998,999,1000system("pause");
return 0;
}

0

Решение

Диапазоны итераторов должны быть выражены как итератор, ссылающийся на первый элемент, и итератор, ссылающийся на «один за другим». Если они равны, это пустой диапазон. Вы этого не делаете.

Чтобы это исправить, if(first+1==last) пункт должен просто вернуться. Второй mergesort(middle+1,last) звонок должен быть mergesort(middle,last), pa должен просто равняться middle-last, pb рассчитывается правильно. И я думаю, что -1 в последнем цикле for следует удалить.

Иметь диапазон, определенный итератором для первого и итератором для последнего, — плохая идея.

2

Другие решения

Ты должен сделать

mergesort(A.begin(),A.end()-1);

На самом деле, end() итератор указывает на элемент после конец вектора. Это не указывает на прошлой элемент вектора.

1

По вопросам рекламы [email protected]