# quickSort: Quicksort for Partial Orderings In rje: Miscellaneous Useful Functions for Statistics

 quickSort R Documentation

## 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.

Robin Evans

`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.

```

rje documentation built on Nov. 12, 2022, 9:06 a.m.