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 ?

Kamin

It won't matter that the pivot or elements equal to the pivot can end up anywhere after a partition step and that the returned index just separates elements <= pivot from elements >= pivot, if the base (terminating) case is changed to when partition size is reduced to 1. I answered with example code. – Miffy

Hoare actually published Find, which is quickselect with his paritioning scheme. See Algorithm 65 in dl.acm.org/doi/pdf/10.1145/366622.366647. The partition method has output variables for the pivot points. – Sadye

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]
}

Miffy

Thanks....this makes a lot of sense. So with this one we must keep partitioning until we get to a one element subarray. Is it then possible that other partitioning schemes that give us the final position of the pivot after each partition can be faster since there we can search after each partition if pivotFinalPos==k? Or is that benefit out-weighted in the long run by the fact that Hoare partitioning is faster? – Kamin

@Kamin - I'm not sure about the performance difference. With Lomuto, a[index of pivot] is always excluded, while with Hoare on random data, a[index from partition] is excluded about 1/2 of the time. – Miffy

Could you explain the last 4 lines of the QuickSelectr code? (j version). Why must we search from (j +1, r) if k > j? (It has infinite recursion if I change it to (j, r)). – Russi

@a6623 - Consider the case where lo = 0, hi = 1, k = 1, a[0] < a[1], p = a[0]. After the partition code, you end up with i = 0, j = 0 (because a[1] > p). If the call is changed from (a, j+1, hi, k) to (a, j, hi, k) you end up with lo = 0, hi = 1 again, resulting in infinite recursion as you found out. – Miffy

Answer 2

I believe the existing answer presents a sub-optimal solution. You can simply amend Hoare's algorithm to return the index of the pivot, re:

because Hoare partitioning does not return the index of the pivot necessarily.

To do this, you select the first element of your array as the pivot and then you essentially ignore it, partitioning the remaining sub-array arr[1:] as you would normally. Then, at the end, you swap arr[0] with the element of the index you normally return.

This works since (vanilla) Hoare's algorithm returns an index idx such that:

• for all j in [lo, idx], arr[j] <= arr[idx]
• for all j in [idx, hi], arr[idx] <= arr[j]

Swapping your pivot with the element at arr[j] maintains this invariant.

Here's an example implementation written in Solidity (since I've had to implement such a thing in a smart contract in the past):

function partition
(
  uint256[] memory arr,
  uint256 lo,
  uint256 hi
)
  public
  pure
  returns (uint256)
{
  uint pivot = arr[lo];
  uint i = lo;
  uint j = hi + 1;

  while (true) {
    do {
      i++;
    } while (i < arr.length && arr[i] < pivot);
    do {
      j--;
    } while (arr[j] > pivot);
    if (i >= j) {
      // swap with pivot
      (arr[lo], arr[j]) = (arr[j], arr[lo]);
      return j;
    }
    (arr[i], arr[j]) = (arr[j], arr[i]);
  }
}

Maki