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)shellSort.insertionSort when the
sorting procedure is called recursively.testSort: the length of a vector of random numbers
to be sorted.is.sorted indicates logically whether the vector is sorted.
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.
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)
Run the code above in your browser using DataLab