quickSort {rje}

Quicksort for Partial Orderings

Description

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.

...

other arguments to f

random

logical - should a random pivot be chosen? (this is recommended) Otherwise middle element is used.

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.

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 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(s)

Robin Evans

References

https://en.wikipedia.org/wiki/Quicksort.

See Also

order.

Examples

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.