QuickSelect with Hoare partition scheme

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

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