Sorting Routines
R implementations of several sorting routines. These implementations are meant for demonstration and lecturing purposes.
is.sorted(a) testSort(n = 1000) bubbleSort(a) insertionSort(a) selectionSort(a) shellSort(a, f = 2.3) heapSort(a) mergeSort(a, m = 10) mergeOrdered(a, b) quickSort(a, m = 3) quickSortx(a, m = 25)
a, b |
Numeric vectors to be sorted or merged. |
f |
Retracting factor for |
m |
Size of subsets that are sorted by |
n |
Only in |
bubbleSort(a) is the well-known “bubble sort” routine; it is
forbiddingly slow.
insertionSort(a) sorts the array one entry at a time; it is slow,
but quite efficient for small data sets.
selectionSort(a) is an in-place sorting routine that is inefficient,
but noted for its simplicity.
shellSort(a, f = 2.3) exploits the fact that insertion sort works
efficiently on input that is already almost sorted. It reduces the gaps
by the factor f; f=2.3 is said to be a reasonable choice.
heapSort(a) is not yet implemented.
mergeSort(a, m = 10) works recursively, merging already sorted parts
with mergeOrdered. m should be between3 and 1/1000 of
the size of a.
mergeOrdered(a, b) works only correctly if a and a
are already sorted.
quickSort(a, m = 3) realizes the celebrated “quicksort algorithm”
and is the fastest of all implementations here. To avoid too deeply nested
recursion with R, insertionSort is called when the size of a subset
is smaller than m.
Values between 3..30 seem reasonable and smaller values are better,
with the risk of running into a too deeply nested recursion.
quickSort(a, m = 25) is an extended version where the split is
calculated more carefully, but in general this approach takes too much
time.
Values for m are 20..40 with m=25 favoured.
testSort(n = 1000) is a test routine, e.g. for testing your
computer power. On an iMac, quickSort will sort an array of
size 1,000,000 in less than 15 secs.
All routines return the vector sorted.
is.sorted indicates logically whether the vector is sorted.
At the moment, only increasingly sorting is possible
(if needed apply rev afterwards).
HwB <hwborchers@googlemail.com>
Knuth, D. E. (1973). The Art of Computer Programming, Volume 3: Sorting and Searching, Chapter 5: Sorting. Addison-Wesley Publishing Company.
sort, the internal C-based sorting routine.
## Not run: testSort(100) a <- sort(runif(1000)); b <- sort(runif(1000)) system.time(y <- mergeSort(c(a, b))) system.time(y <- mergeOrdered(a, b)) is.sorted(y) ## End(Not run)
Please choose more modern alternatives, such as Google Chrome or Mozilla Firefox.