장소 무작위 추출 알고리즘

Question

우리는 현재 알고리즘을 연구하고 있으므로 숙제와 관련없는 작업 임에도 불구하고이 질문을 숙제라고 표시했습니다. 그냥 안전 해.

우리는 방금 무작위 추출 알고리즘을 연구했으며 논리는 단순 해 보입니다. 목록에서 요소를 선택한 다음 요소를 올바른 위치에 놓습니다. 그런 다음 색인의 요소가 제자리에 올 때까지 한 하위 목록에서 프로세스를 반복하십시오. 여기서 index는 정렬 목록에서 원하는 요소의 위치입니다.

이것은 빠른 정렬 알고리즘의 수정 된 버전이어야합니다. 그러나 우리는 하나의 하위 목록만을 정렬하며, 두 개의 하위 목록은 정렬하지 않습니다. 따라서 성능이 향상되었습니다 (크게).

내가 성공적으로 외부 저장하여이 알고리즘을 구현할 수 있습니다 (C를 ++ 및 0 기반 배열의) :

int r_select2(vector<int>& list, int i) 
{ 
    int p = list[0]; 

    vector<int> left, right; 

    for (int k = 1; k < list.size(); ++k) 
    { 
     if (list[k] < p) left.push_back(list[k]); 
     else  right.push_back(list[k]); 
    } 

    int j = left.size(); 

    if (j > i) p = r_select2(left, i); 
    else if (j < i) p = r_select2(right, i - j - 1); 

    return p; 
} 

그러나, 내가 (자리에서)에서 현장 사용하여 알고리즘을 구현하고자하고, 사용하지 추가 서브 어레이. 나는 이것이 쉬운/쉬운 일이되어야한다고 생각한다. 하지만 어딘가에서 제 현장 버전이 잘못되었습니다. 아마 그냥 늦게 나는 잠이 필요하지만, 나는 다음과 같은 버전이 실패하는 이유의 근본 원인 볼 수 없습니다 : 두 예에서

int r_select(vector<int>& list, int begin, int end, int i) 
{ 
    i = i + begin; 
    int p = list[begin]; 

    if (begin < end) 
    { 
     int j = begin; 
     for (int k = begin + 1; k < end; ++k) 
     { 
     if (list[k] < p) 
     { 
      ++j; 
      swap(list[j], list[k]); 
     } 
     } 

     swap(list[begin], list[j]); 

     if (j > i) p = r_select(list, begin, j, i); 
     else if (j < i) p = r_select(list, j + 1, end, i - j); 
    } 

    return p; 
} 

를 첫 번째 요소는 디자인을 유지하는 피벗으로 사용되는 단순한. 두 예제 모두 i은 내가 원하는 요소의 인덱스입니다.

두 번째 예제가 실패한 아이디어는 무엇입니까? 간단한 오류인가요?

감사합니다.

Answer 1

이 비린내가 소리 :

i = i + begin; 
... 
r_select(list, begin, j, i);