Найти Kth наибольший int в массиве

Question

Я пытаюсь использовать quickselect в C++ для этого, но он продолжает возвращать мне 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

< и > в вашем коде обратный в partition() как @Dietmar Kühl, упомянув, изменив их, он работает правильно.

Кроме того, мое предложение состоит в том, чтобы использовать обычную 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; 
}