Implements the quicksort algorithm for partial orderings based on pairwise
comparisons.
Usage
quickSort(x, f = greaterThan, random = TRUE)
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.
random
logical - should a random pivot be chosen? (this is recommended)
Otherwise middle element is used.
Value
Returns an integer vector giving each element's position in the order
(minimal element(s) is 1, etc).
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 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.
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 order.
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.