Алгоритм quickSelect для возврата k-го наименьшего элемента

Question

Я следовал за quickSelect, чтобы понять и реализовать алгоритм quickSelect. В одном я не уверен: почему они это делают? k-pivot а также pivot-first+1,

Хотя моя реализация в точности похожа на эту ссылку, она не работает.

#include <stdio.h>
#include <string.h>

#define DEBUG 1

#define debug(fmt, ...)\
    do{\
        if(DEBUG)\
            fprintf(stdout, "%s(%d) :   " fmt "\n", __FUNCTION__, __LINE__, __VA_ARGS__);\
    }while(0)

#define swap(a, b)\
    do{\
        if(a != b) {\
            a = a ^ b;\
            b = a ^ b;\
            a = a ^ b;\
        }\
    }while(0)


int
partition(int *a, int low, int high)
{
    int i = low, j = high;

    int pivot = a[i];
    i++;
    while(i < j)
    {
    while(pivot >= a[i])
        i++;
    while(pivot < a[j])
        j--;
    if(i < j)
        swap(a[i], a[j]);
    }

    swap(a[low], a[j]);
    return j;
}


int
quick_select(int *a, int start, int end, int k)
{
    if(start < end)
    {
    int pivot = partition(a, start, end);

    if(k < (pivot - start + 1))
       return quick_select(a, start, pivot, k);
    else if( k > (pivot - start + 1))
       return quick_select(a, pivot+1, end, k - pivot);
    else
    return a[pivot];
    }
}

int
main()
{
    int a[100], k, n;
    int ret, i;

    while(1)
    {
    printf("# of items  :   ");
    scanf("%d", &n);

    printf("Items   :   ");
    for(i = 0; i<n; i++)
        scanf("%d", &a[i]);

    printf("<k> :   ");
    scanf("%d", &k);

    ret = quick_select(a, 0, n-1, k);
    printf("[%d] smallest element = [%d]\n", k, ret);
    }

    return 0;
}

Выход:

./a.out 
# of items  :   10
Items   :    1 2 3 4 5 6 7 8 9 10
<k> :   9
[9] smallest element = [32767]

Answer 1

Во-первых, номан прав. Второй быстрый выбор

quick_select(a, pivot+1, end, k - (pivot-start+1));

Во-вторых, обратите внимание на значение входных данных. start а также end абсолютная позиция в исходном списке, соответствующая текущему рекурсивному вызову. k это относительная позиция в текущем списке [start, end]

1. pivot-start+1 это относительная позиция индекса pivot в текущем подсписке, начиная с start,
2. k - (pivot-start+1) (в вашем alg k - pivot) - относительная позиция k наименьшего элемента в списке, начиная с точки разворота. Например, 4-й самый маленький элемент в списке из 6 [1, 2, 3, 4, 5, 6] является вторым самым маленьким в подсписке, начинающемся с 3 [3, 4, 5, 6]

Answer 2

Просто вы не делали pivot-1 в одном случае и не вычитали правильное значение из K, чтобы найти следующий K.

Предположим, у вас есть 8 чисел, и вы получите пивот как 5. Что это означает 5? Это означает, что число в 5-м индексе - это 5-й наименьший элемент, если вы сортируете в неубывающем порядке, а все числа, меньшие 5-го индекса, меньше этого значения. Так что, если вы ищете 7 самых маленьких чисел (давайте назовем это K), где вы должны искать? Вы должны искать в 6-8 правильно? Но что должно произойти с числом K, если вы все еще ищете 7 самых маленьких в диапазоне от 6 до 8? Без прав?

Вы не думаете, что вы должны вычесть 6(от 0 до 5) чисел из 7? Если вы все еще думаете, нет? Тогда читайте дальше, иначе перестаньте читать здесь.

Предположим, у вас есть 5 младших братьев, и вы самый высокий среди них. Слепой приходит в ваш дом и хочет знать, кто является 5-м по высоте среди всех вас. Итак, вы скажете ему сказать два имени, и вы скажете ему, кто самый высокий среди этих братьев. Это единственный вопрос, который он может задать, чтобы узнать 5-й самый высокий. Так что он делает что-то похожее на быструю сортировку. Если он выберет вашего третьего брата в качестве точки поворота и расположит ваших братьев, чей рост меньше трети слева и других справа. После этого, если он посчитает, где стоит ваш третий брат, он узнает, что ваш третий брат третий по высоте. в твоем доме. Теперь, где он должен искать 5-й самый высокий, очевидно справа? Нет?

Но он не знает, где 4-й самый высокий стоит направо. Правильно? Все, что он знает, это то, что 4-й и 5-й самый высокий направо. Таким образом, у вас есть два человека, стоящих направо, и оба имеют высоту больше 3-го, а слепой хочет знать 5-е самое высокое, но среди этих двух, вы должны искать 4-е самое высокое или 2-е самое высокое (5-3) в правой группе (диапазон от 4 до 5)?

Я уверен, что теперь вы бы поняли.

quick_select(int *a, int start, int end, int k)
{
    if(start < end)
    {
        int pivot = partition(a, start, end);

        if(k < (pivot - start + 1))
            return quick_select(a, start, pivot-1, k);
        else if( k > (pivot - start + 1))
            return quick_select(a, pivot+1, end, k - (pivot-start+1));
        else
            return a[pivot];
    }
}