Sorting: Generics for in-RAM sorting and ordering

In bit: Classes and Methods for Fast Memory-Efficient Boolean Selections

Generics for in-RAM sorting and ordering

Description

These are generic stubs for low-level sorting and ordering methods implemented in packages 'bit64' and 'ff'. The ..sortorder methods do sorting and ordering at once, which requires more RAM than ordering but is (almost) as fast as as sorting.

Usage

ramsort(x, ...)

ramorder(x, i, ...)

ramsortorder(x, i, ...)

mergesort(x, ...)

mergeorder(x, i, ...)

mergesortorder(x, i, ...)

quicksort(x, ...)

quickorder(x, i, ...)

quicksortorder(x, i, ...)

shellsort(x, ...)

shellorder(x, i, ...)

shellsortorder(x, i, ...)

radixsort(x, ...)

radixorder(x, i, ...)

radixsortorder(x, i, ...)

keysort(x, ...)

keyorder(x, i, ...)

keysortorder(x, i, ...)

Arguments

x	a vector to be sorted by ramsort and ramsortorder, i.e. the output of sort
...	further arguments to the sorting methods
i	integer positions to be modified by ramorder and ramsortorder, default is 1:n, in this case the output is similar to order

Details

The sort generics do sort their argument 'x', some methods need temporary RAM of the same size as 'x'. The order generics do order their argument 'i' leaving 'x' as it was, some methods need temporary RAM of the same size as 'i'. The sortorder generics do sort their argument 'x' and order their argument 'i', this way of ordering is much faster at the price of requiring temporary RAM for both, 'x' and 'i', if the method requires temporary RAM. The ram generics are high-level functions containing an optimizer that chooses the 'best' algorithms given some context.

Value

These functions return the number of NAs found or assumed during sorting

Index of implemented methods

generic	ff	bit64
ramsort	ramsort.default	ramsort.integer64
shellsort	shellsort.default	shellsort.integer64
quicksort		quicksort.integer64
mergesort	mergesort.default	mergesort.integer64
radixsort	radixsort.default	radixsort.integer64
keysort	keysort.default
generic	ff	bit64
ramorder	ramorder.default	ramorder.integer64
shellorder	shellorder.default	shellorder.integer64
quickorder		quickorder.integer64
mergeorder	mergeorder.default	mergeorder.integer64
radixorder	radixorder.default	radixorder.integer64
keyorder	keyorder.default
generic	ff	bit64
ramsortorder		ramsortorder.integer64
shellsortorder		shellsortorder.integer64
quicksortorder		quicksortorder.integer64
mergesortorder		mergesortorder.integer64
radixsortorder		radixsortorder.integer64
keysortorder

Note

Note that these methods purposely violate the functional programming paradigm: they are called for the side-effect of changing some of their arguments. The rationale behind this is that sorting is very RAM-intensive and in certain situations we might not want to allocate additional memory if not necessary to do so. The sort-methods change x, the order-methods change i, and the sortoder-methods change both x and i You as the user are responsible to create copies of the input data 'x' and 'i' if you need non-modified versions.

Author(s)

Jens Oehlschlägel <[e-mail]>

See Also

sort and order in base R, bitsort for faster inteer sorting

bit documentation built on Sept. 20, 2024, 5:08 p.m.