중앙값 3, 반복자가있는 quicksort

정렬 할 벡터의 첫 번째, 마지막 및 중심 요소의 중앙값을 취하여 quicksort의 피벗을 선택하려고합니다. int의 범위에서 많은 구현을 보았지만 iterators를 사용하여 구현하려고했습니다. (어쨌든 다른 점은 없습니다). 그러나, 내 코드 dosent 꽤하고 싶어. T가 int 일 때 작동하지만 다른 클래스에서는 시간이 초과됩니다. 어떤 아이디어?중앙값 3, 반복자가있는 quicksort

template <class T> 
int ParallelSort::partition(typename vector<T>::iterator &start, typename  vector<T>::iterator &end) 
{ 
int Index = (end-start)/2; 
T tmpSwap = start[Index]; 
//the three if statement get the three part median for the vector. 
if(start[Index] < *start) 
{ 
    start[Index] = *start; 
    *start = tmpSwap; 
} 
if(*end < *start) 
{ 
    tmpSwap = *end; 
    *end = *start; 
    *start = tmpSwap; 
} 
if(*end < start[Index]) 
{ 
    tmpSwap = start[Index]; 
    start[Index] = *end; 
    *end = tmpSwap; 
} 
T pivot = start[Index]; 
//rest of the code ..... 
//i'm sure that the rest of the code works correctly

출처

2013-03-25 Sid

첫째, 당신은 typename std::vector<T>::size_type하지 int를 사용한다 : 다음은 코드입니다. 둘째, std::distance을 사용하여 typename std::vector<T>::difference_type에 저장되어야하는 두 개의 반복기 간의 차이점을 찾습니다. 마지막으로 반복자는 일반적으로 참조가 아닌 값으로 전달됩니다.

end을 역 참조하는 것이 문제 일 수 있습니다. 이것은 정의되지 않은 동작입니다. 아마도 --end을 역 참조하려는 것입니다.

또한 Iterators의 전체적인 점은 특정 컨테이너 (이론적으로는 어쨌든)에만 국한되지 않기 때문입니다. 이것은 아마도 서명과 함께 작성되어야합니다 :

출처

2013-03-25 03:27:44 Yuushi

나는이 함수에 전달되기 전에 이미'end'을 감소시키고 있습니다. 그래서 나는 그 것이 문제라고 생각하지 않습니다. size_type int 유형을 변경하고 또한 difference_type 시도했지만 dosent 작동합니다. – Sid

중앙값 3, 반복자가있는 quicksort

답변

관련 문제