배열에서 K 번째 가장 큰 정수를 찾으십시오

Question

나는이 작업을하기 위해 C++에서 quickselect를 사용하려하지만 k 번째 가장 큰 요소 대신 k 번째로 작은 요소를 반환합니다. 내 논리는 어디에서 잘못 되었습니까?

int partition(int* input, int p, int r) 
{ 
    int pivot = input[r]; 

    while (p < r) 
    { 
     while (input[p] < pivot) 
      p++; 

     while (input[r] > pivot) 
      r--; 

     if (input[p] == input[r]) 
      p++; 
     else if (p < r) { 
      int tmp = input[p]; 
      input[p] = input[r]; 
      input[r] = tmp; 
     } 
    } 

    return r; 
} 

int quick_select(int* input, int p, int r, int k) 
{ 
    if (p == r) return input[p]; 
    int j = partition(input, p, r); 
    int length = j - p + 1; 
    if (length == k) return input[j]; 
    else if (k < length) return quick_select(input, p, j - 1, k); 
    else return quick_select(input, j + 1, r, k - length); 
} 

k 번째로 작은 요소 대신 k 번째로 큰 값으로 변경하려면 어떻게해야합니까?

Answer 1

< 및 >은 @Dietmar Kühl이 언급 한대로 partition()에서 역순으로 바뀌어 올바르게 작동합니다.

는 게다가, 내 제안은 그 두 개의 인덱스 같은 방향으로 이동하는과 그들 중 하나가 결코 다른 능가하지, 다음과 같이 퀵의 정상적인 partition()을 사용하는 것입니다. 혼란스럽게 만드는 것은 쉽지 않습니다.

int partition(int *input, int p, int r) { 
    int pivot,i,j,tmp; 
    pivot = input[r]; 
    i = p-1; 
    for (j=p;j<=r-1;j++) { 
     if (input[j]>= pivot) { 
      i++; 
     tmp = input[i]; 
     input[i] = input[j]; 
     input[j] = tmp; 
     } 
    } 
    tmp = input[i+1]; 
    input[i+1] = input[r]; 
    input[r] = tmp; 
    return i+1; 
}