QuickSelect со схемой разбиения Hoare

Question

Возможно ли реализовать алгоритм QuickSelect с использованием разбиения Hoare?

По крайней мере, на первый взгляд кажется, что это невозможно сделать, потому что разбиение Hoare не возвращает индекс основной точки обязательно.

Я что-то упустил?

Answer 1

При использовании схемы разбиения Hoare, поскольку стержень или элементы, равные стержню, могут заканчиваться где угодно после шага разделения, базовый (завершающий) случай возникает, когда размер раздела уменьшается до одного элемента. Пример кода. QuickSelectr является актуальной функцией. QuickSelect проверяет параметры.

int QuickSelectr(int a[], int lo, int hi, int k )
{
    if (lo == hi)                           // recurse until lo == hi
        return a[lo];
    int p = a[(lo+hi)/2];                   // Hoare partition
    int i = lo - 1;
    int j = hi + 1;
    while (1){
        while (a[++i] < p);
        while (a[--j] > p);
        if (i >= j)
            break;
        std::swap(a[i], a[j]);
    }
    if(k <= j)
        return QuickSelectr(a, lo, j-0, k); // include a[j]
    else
        return QuickSelectr(a, j+1, hi, k); // exclude a[j]
}

// parameter check
int QuickSelect(int *a, int lo, int hi, int k)
{
    if(a == (int *)0 || k < lo || k > hi || lo > hi)
        return 0;
    return QuickSelectr(a, lo, hi, k);
}

---

Использование i вместо j для разделения:

int QuickSelectr(int a[], int lo, int hi, int k )
{
    if (lo == hi)                           // recurse until lo == hi
        return a[lo];
    int p = a[(lo+hi+1)/2];                 // Hoare partition
    int i = lo - 1;
    int j = hi + 1;
    while (1){
        while (a[++i] < p);
        while (a[--j] > p);
        if (i >= j)
            break;
        std::swap(a[i], a[j]);
    }
    if(k < i)
        return QuickSelectr(a, lo, i-1, k); // exclude a[i]
    else
        return QuickSelectr(a, i+0, hi, k); // include a[i]
}