pracma (version 1.8.8)

sorting: Sorting Routines

Description

R implementations of several sorting routines. These implementations are meant for demonstration and lecturing purposes.

Usage

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)

Arguments

a, b

Numeric vectors to be sorted or merged.

f

Retracting factor for shellSort.

m

Size of subsets that are sorted by insertionSort when the sorting procedure is called recursively.

n

Only in testSort: the length of a vector of random numbers to be sorted.

Value

• All routines return the vector sorted.

  is.sorted indicates logically whether the vector is sorted.

Details

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.

References

Knuth, D. E. (1973). The Art of Computer Programming, Volume 3: Sorting and Searching, Chapter 5: Sorting. Addison-Wesley Publishing Company.

See Also

sort, the internal C-based sorting routine.

Examples

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)