我一直在努力进行合并排序,到目前为止,我认为一切正常,除了我必须比较左右数组的部分。帮助!(这是一个家庭作业,所以它必须与这个伪代码几乎相同:
/*MERGESORT(A, p, r)]
if p < r
q = (p+r)/2
MERGESORT(A,p,q)
MERGESORT(A,q + 1, r)
MERGE(A,p,q,r)
MERGE(A,p,q,r)
n1 = q - p + 1
n2 = r - q
let L[1...n1 + 1] and R[1...n2 + 1] be new arrays
for i = 1 to n1
L[i] = A[p + i - 1]
for j = 1 to n2
R[j] = A[q + j]
L[n1 + 1] = INFINITY
R[n2 + 1] = INFINITY
i = 1
j = 1
for k = p to r
if L[i] <= R[j]
A[k] = L[i]
i = i + 1
else
A[k] = R[j]
j = j + 1*/
这些是归并排序函数 注意:忽略整数类型,它什么都不做。
void CensusData::mergeSort(int type) {
if(type == 0) //STOPPED FOR DEBUGGING
MERGE_SORT(type, 0, data.size() - 1);
}
void CensusData::MERGE_SORT(int type, int p, int r){
//int q;
//cout << "data size " << data.size() << endl;
std::cout << "MERGE_SORT START ///("<< p << ", " << r << ")" <<std::endl;
if(p < r)
{
int q = (p + r)/2;
MERGE_SORT(type, p, q);
MERGE_SORT(type, q + 1, r);
MERGE(type, p, q ,r);
}
}
void CensusData::MERGE(int type, int p, int q, int r){
if(type == 0)
{
std::cout << "MERGING WITH: (" << p << ", "<< q <<", " << r<< ")"<< std::endl;
//int n1;
//int n2;
int n1 = q - p + 1;
int n2 = r - q;
cout << "N1: " << n1 <<" N2:" << n2 << endl;
Record* L[n1 + 1];
Record* R[n2 + 1];
L[n1 + 1] = NULL;
R[n2 + 1] = NULL;
for(int i = 0; i < n1; i++)
{
//if (L[i] == NULL)
//continue;
cout << "P, I: " << p <<", "<< i<< endl;
cout << "filling array L: " << data[p + i]->population << endl;
L[i] = data[p + i];
cout<< L[i]->population << endl;
}
//cout << "J: " << j << endl;
for(int j = 0; j < n2; j++)
{
//if(R[j] == NULL)
//continue;
cout << "filling array R: " << data[q + j + 1]->population<<endl;
R[j] = data[q + j + 1];
cout << R[j]->population << endl;
}
//THIS IS WHERE I THINK THE PROBLEMS ARE OCCURING FROM VVVVVVVVVVV
int i = 0;
int j = 0;
for(int k = p; k <= r; k++)
{
if(L[i]->population < R[j]->population)
{
cout << "TRUE" << endl;
data[k] = L[i];
i = i + 1;
}
else if (L[i]->population > R[j]->population)
{
cout << "FALSE" << endl;
data[k] = R[j];
j = j + 1;
}
}
/*std::vector<Record*>::iterator it = data.begin();
while (it != data.end()) {
std::cout << *(*it)->city << ", "
<< *(*it)->state << ", "
<< (*it)->population << std::endl;
it++;}*/
}
}
输入:::
Vina, California, 237
San Francisco, California, 812826
Santa Fe, New Mexico, 68642
输出:::
Vina, California, 237
Santa Fe, New Mexico, 68642
Program received signal SIGSEGV, Segmentation fault.
0x00445cf7 in std::basic_ostream<char, std::char_traits<char> >& std::operator<< <char, std::char_traits<char>, std::allocator<char> >(std::basic_ostream<char, std::char_traits<char> >&, std::basic_string<char, std::char_traits<char>, std::allocator<char> > const&) ()
at /usr/lib/gcc/i686-pc-cygwin/3.4.4/include/c++/iostream:77
77 static ios_base::Init __ioinit;
输入示例 2:::
Vina, California, 237
San Francisco, California, 812826
Santa Fe, New Mexico, 68642
Roseville, California, 1293
New York, New York, 283822
pieland, Conneticut, 283822
的输出::::
Program received signal SIGSEGV, Segmentation fault.
0x004031ae in CensusData::MERGE (this=0x28aa40, type=0, p=0, q=2, r=5)
at CensusDataSorts.cpp:105
105 if(L[i]->population < R[j]->population)