QuickSelect with Hoare partition scheme

Question

Is it possible to implement QuickSelect algorithm using Hoare partitioning?

At least at first glance it seems that it cannot be done because Hoare partitioning does not return the index of the pivot necessarily.

Am I missing something ?

Answer 1

With Hoare partition scheme, since the pivot or elements equal to the pivot can end up anywhere after a partition step, the base (terminating) case occurs when the partition size is reduced to a single element. Example code. QuickSelectr is the actual function. QuickSelect validates the parameters.

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);
}

---

Using i instead of j for the split:

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]; // Carefully note the +1 compared
                            // to the variant where we use j
    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]
}