Segfault가 벡터를 정렬하는 동안

Question

연습으로 템플릿에 quicksort 알고리즘을 구현했으며 요소 수가 적은 (최대 약 760 개) 벡터에 대해서는 "잘 작동하지만"요소 수가 많으면 seqfault를 제공합니다. 다른 사람이 내가 잘못하고있는 것을 말해 줄 수 있습니까?

template< typename Vector, typename VecElem > void qsort(Vector *pv) 
{ 
    if (pv->size()<=1) return; 

    VecElem p; 
    Vector *pvl=new Vector,*pvr=new Vector; 

    p = pv->back(); 
    pv->pop_back(); 
    pvr->push_back(p); 
    for (auto it=pv->begin();it!=pv->end();it++) 
    { 
     if (*it < p) pvl->push_back(*it); 
     else pvr->push_back(*it); 
    } 
    qsort<Vector,VecElem>(pvl); 
    qsort<Vector,VecElem>(pvr); 
    if (pvl->size()) *pv = *pvl; 
    if (pvr->size()) std::copy(pvr->begin(), pvr->end(), std::back_inserter(*pv)); 
    delete pvl; 
    delete pvr; 
} 

Answer 1

다른 사람이 지적한 것처럼 구현은 효율적이지 않습니다. 오름차순 데이터 정렬. 그러나 이것이 귀하의 segfault에 대한 이유는 아닙니다. 코드의 문제는 파티셔닝 단계에서 피벗 요소를 제외하지 않는다는 것입니다.

두 개의 동일한 요소 (예 : {0,0})로만 이루어진 벡터를 정렬하려고하면됩니다. 무한 루프가 반복됩니다.

문제를 해결하려면 두 벡터를 모두 정렬 한 후에 피벗 요소를 삽입하십시오.

아마이 (적어도 스택 오버 플로우를 해결) 작동 :

pvr->push_back(p); // remove this line 

// and insert it later... 
qsort<Vector,VecElem>(pvl); 
qsort<Vector,VecElem>(pvr); 
pvl->push_back(p); // this line is new