Implements the quicksort algorithm for partial orderings based on pairwise
comparisons.
Usage
quickSort(x, f = greaterThan, ..., random = TRUE)
Value
Returns an integer vector giving each element's position in the
order (minimal element(s) is 1, etc).
Arguments
x
A list or vector of items to be sorted.
f
A function on two arguments for comparing elements of x.
Returns -1 if the first argument is less than the second, 1
for the reverse, and 0 if they are equal or incomparable.
...
other arguments to f
random
logical - should a random pivot be chosen? (this is
recommended) Otherwise middle element is used.
Warning
Output may not be consistent for certain partial orderings
(using random pivot), see example below. All results will be consistent
with a total ordering which is itselft consistent with the true partial
ordering.
f is not checked to see that it returns a legitimate partial order,
so results may be meaningless if it is not.
Author
Robin Evans
Details
Implements the usual quicksort algorithm, but may return the same positions
for items which are incomparable (or equal). Does not test the validity of
f as a partial order.
If x is a numeric vector with distinct entries, this behaves just
like rank.
set.seed(1)
quickSort(powerSet(1:3), f=subsetOrder)
quickSort(powerSet(1:3), f=subsetOrder)
# slightly different answers, but both correposnding# to a legitimate total ordering.