2
$\begingroup$

Consider the following computational problem (or rather, task):

Given:

  • An array of $A$ of (not necessarily distinct) elements from a fully-ordered finite domain
  • An ordered sequence pivot values $p_1 \ldots p_m$ (i.e. such that $i < j \implies p_i < p_j$).

Output:

A partition of $A$ into $m+1$ parts (be they sets or shorter arrays), denoted $A'_0 \ldots A'_m$ , such that if $i < j$ and $x \in A'_i$ then $x < p_j$.

One could call this computing a "histogram with variable-size bins", or "m-pivoting", or "m-way ordered partitioning", etc.

But are there names for this task which are more commonly used than others?

PS - If it helps, we can relax the requirement on the pivots to $p_i \leq p_j$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.