来自CLRS的水槽问题

Question

在运行此代码时，我将收到一个分段错误。

#include <iostream>
#include <vector>
using namespace std;

void quicksort(vector<int>&,vector<int>&,int,int);
int partationR(vector<int>&,int,int);
int partationB(vector<int>&,int,int);
int main()
{
vector<int> R = {2,5,3,6,4,8,7,9};
vector<int> B = {8,1,2,5,7,3,6,9};
int p=B[0];
int q=10;
vector<int> RB;
RB.reserve( R.size() + B.size() );
RB.insert( RB.end(), R.begin(), R.end() );
RB.insert( RB.end(), B.begin(), B.end() );

cout<<":::::::::Original::::::::"<<endl;
for(int i=0;i<RB.size();i++)
    cout<<RB[i]<<" ";
cout<<endl;

quicksort(R,B,p,q);

cout<<":::::::::Sorted::::::::::"<<endl;
for(int i=0;i<RB.size();i++)
    cout<<RB[i]<<" ";
cout<<endl;
}

void quicksort(vector<int>& R, vector<int>& B, int p, int q)
{
    int r,s;
        r=partationR(R,p,q);
        s=partationB(B,p,q);
        quicksort(R,B,p,r);
        quicksort(R,B,r+1,q);
        quicksort(R,B,p,s);
        quicksort(R,B,s+1,q);
}

int partationR(vector<int>& R, int p, int q)
{
    int x=R[p];
    int i = 0;
    int j;
    for(j=i+1;j<q;j++)
    {
        if(R[j]<=x)
        {
            i=i+1;
            swap( R[i],R[j] );

        }
    }
    swap( R[i], R[p] );
    return i;
}

int partationB(vector<int>& B, int p, int q)
{
    int y = B[p];
    int k = 0;
    int l;
    for(l=k+1;l<q;l++)
    {
        if (B[k]<=y)
        {
            k=k+1;
            swap( B[k],B[l] );
        }
    }
    swap( B[k],B[p] );
    return k;
}

GDB的输出

(gdb) c
Continuing.
:::::::::Original::::::::
2 5 3 6 4 8 7 9 8 1 2 5 7 3 6 9 

Program received signal SIGSEGV, Segmentation fault.
0x00000000004014e6 in std::vector<int, std::allocator<int> >::operator[] (
this=<error reading variable: Cannot access memory at address      0x7fffff7feff8>, 
__n=<error reading variable: Cannot access memory at address     0x7fffff7feff0>)
    at /usr/include/c++/5/bits/stl_vector.h:779
779       operator[](size_type __n) _GLIBCXX_NOEXCEPT
(gdb) kill

Answer 1

算法中有一些奇怪的地方，您正在对R和B进行排序，然后考虑RB排序。也许你想把RB，排序，而不是？或想将R和B和分别排序，然后插入RB

无论如何，分割错误通常指向超出绑定的数据访问，也就是说，在这种情况下，向量元素被计算错误的位置。一种可能的误判：

int p=B[0]; //=8
...
//quicksort(R,B,p,q); -> partationB(B,p,q);
int y = B[p]; // = B[8], however size of B is 8    

类似的情况发生在q上。因此，它看起来应该只是简单地：

int p=0;
int q=7;

因为它们应该是向量划分的初始指标。