quicksort: Quick Sort Algorithm

In stufield/stuRpkg: Stu's Utilities Package

Quick Sort Algorithm

Description

The quick-sort algorithm is a computer science "divide-and-conquer" algorithm used here as a applied example of recursion. Sometimes called partition-exchange sort, is an efficient sorting algorithm. Developed by British computer scientist Tony Hoare in 1959 and published in 1961, it is still a commonly used algorithm for sorting. When implemented well, it can be about two or three times faster than its main competitors, merge-sort and heapsort.

Usage

quicksort(x)

Arguments

x	An vector to be sorted via the quick-sort algorithm.

Details

It works by selecting a 'pivot' element from the array and partitioning the other elements into two sub-arrays, according to whether they are less than or greater than the pivot. The sub-arrays are then sorted recursively. This can be done in-place, requiring small additional amounts of memory to perform the sorting.

Value

A sorted vector or x.

Source

https://en.wikipedia.org/wiki/Quicksort

References

tony Hoare (1959).

Examples

set.seed(101)
x <- sample(LETTERS)
quicksort(x)

# numeric x; compared to `base::sort()`
# this implementation is *much* slower
y <- sample(1:1000)
bench::mark(
  base      = sort(y),
  quicksort = quicksort(y)
)

stufield/stuRpkg documentation built on April 2, 2022, 2:05 p.m.