[C ++] 중복 된 요소로 인해 빠른 선택 알고리즘이 실패 함

코드에 몇 가지 문제가 있습니다.

• 첫째, 함수 quick_select()에서 직접 비교 pivotIndex하고 n있습니다. (가) 때문에 left항상 0이, 당신은 비교해야 n같다 왼쪽 부분의 길이pivotIndex - left + 1 .
• 를 재귀 적으로 n > length호출 하면 , quick_select(a, pivotIndex + 1, right, n)이때 전체 벡터의 N 번째 요소가 오른쪽 부분에 있고, 오른쪽 부분의 (N-(pivotIndex-left + 1)) 번째 요소입니다. 벡터의. 코드는 quick_select(a, pivotIndex + 1, right, n - (pivotIndex - left + 1) )(n은 1 기반) 이어야합니다 .
• Hoare의 분할 알고리즘을 사용하고 있으며 잘못 구현 한 것 같습니다. 작동하더라도, 때 호어 파티션이 종료, 그와 같은 j 값을 반환 A[p...j] ≤ A[j+1...r]하지만, 우리는 원하는 A[p...j-1] ≤ A[j] ≤ A[j+1...r]에 quick_select(). 그래서 다른 포스트에rand_partition() 쓴 Lomuto의 분할 알고리즘을 기반으로

다음은 벡터의 가장 작은 요소 인 quick_select()N 번째 ( n은 1부터 시작 함 ) 를 반환 하는 고정 입니다 .

int quick_select(vector<int> &a, int left, int right, int n)
{
    if ( left == right ) 
            return a[left];
                int pivotIndex = partition(a, left, right);
                
                    int length = pivotIndex - left + 1;
                        if ( length == n) 
                                return a[pivotIndex];
                                    else if ( n < length ) 
                                            return quick_select(a, left, pivotIndex - 1, n);
                                                else 
                                                        return quick_select(a, pivotIndex + 1, right, n - length);
                                                        }
                                                        

그리고 이 는 IS rand_partition():

int rand_partition(vector<int> &arr, int start, int end)
{
    int pivot_index = start + rand() % (end - start + 1);
        int pivot = arr[pivot_index];
        
            swap(arr[pivot_index], arr[end]); // swap random pivot to end.
                pivot_index = end;
                    int i = start -1;
                    
                        for(int j = start; j <= end - 1; j++)
                            {
                                    if(arr[j] <= pivot)
                                            {
                                                        i++;
                                                                    swap(arr[i], arr[j]);
                                                                            }
                                                                                }
                                                                                    swap(arr[i + 1], arr[pivot_index]); // swap back the pivot
                                                                                    
                                                                                        return i + 1;
                                                                                        }
                                                                                        

srand()먼저 호출 하여 난수 생성기를 초기화하면을 호출 할 때 임의의 유사 번호를 얻을 수 있습니다 rand().
위의 기능을 테스트하는 드라이버 프로그램 :

int main()
{
    int A1[] = {1, 0, 3, 5, 0, 8, 6, 0, 9, 0};
        vector<int> a(A1, A1 + 10);
            cout << "6st order element " << quick_select(a, 0, 9, 6) << endl;
                vector<int> b(A1, A1 + 10); // note that the vector is modified by quick_select()
                    cout << "7nd order element " << quick_select(b, 0, 9, 7) << endl;
                        vector<int> c(A1, A1 + 10);
                            cout << "8rd order element " << quick_select(c, 0, 9, 8) << endl;
                                vector<int> d(A1, A1 + 10);
                                    cout << "9th order element " << quick_select(d, 0, 9, 9) << endl;
                                        vector<int> e(A1, A1 + 10);
                                            cout << "10th order element " << quick_select(e, 0, 9, 10) << endl;
                                            }
                                            

출처
https://stackoverflow.com/questions/22080055