Quicksort

The fastest known Sorting Algorithm (on average, and for a large number of elements), requiring steps. Quicksort is a recursive algorithm which first partitions an array according to several rules (Sedgewick 1978):

1. Some key is in its final position in the array (i.e., if it is the th smallest, it is in position).

2. All the elements to the left of are less than or equal to . The elements , , ..., are called the ``left subfile.''

3. All the elements to the right of are greater than or equal to . The elements , ..., are called the ``right subfile.''

Quicksort was invented by Hoare (1961, 1962), has undergone extensive analysis and scrutiny (Sedgewick 1975, 1977, 1978), andis known to be about twice as fast as the next fastest Sorting algorithm. In the worst case, however, quicksort is aslow algorithm (and for quicksort, ``worst case'' corresponds to already sorted).

References

Aho, A. V.; Hopcroft, J. E.; and Ullmann, J. D. Data Structures and Algorithms. Reading, MA: Addison-Wesley, pp. 260-270, 1987.

Hoare, C. A. R. ``Partition: Algorithm 63,'' ``Quicksort: Algorithm 64,'' and ``Find: Algorithm 65.'' Comm. ACM 4, 321-322, 1961.

Hoare, C. A. R. ``Quicksort.'' Computer J. 5, 10-15, 1962.

Press, W. H.; Flannery, B. P.; Teukolsky, S. A.; and Vetterling, W. T. ``Quicksort.'' §8.2 in Numerical Recipes in FORTRAN: The Art of Scientific Computing, 2nd ed. Cambridge, England: Cambridge University Press, pp. 323-327, 1992.

Sedgewick, R. Quicksort. Ph.D. thesis. Stanford Computer Science Report STAN-CS-75-492. Stanford, CA: Stanford University, May 1975.

Sedgewick, R. ``The Analysis of Quicksort Programs.'' Acta Informatica 7, 327-355, 1977.

Sedgewick, R. ``Implementing Quicksort Programs.'' Comm. ACM 21, 847-857, 1978.

• Cevian
• Cevian Conjugate Point
• Cevian Transform
• Cevian Triangle
• Chain
• Chained Arrow Notation
• Chainette
• Chain Fraction
• Chain (Graph)
• Chain Rule
• Chair
• Chaitin's Constant
• Chaitin's Number
• Chaitin's Omega
• Champernowne Constant
• Change of Variables Theorem
• Chaos
• Chaos Game
• Character (Group)
• Characteristic Class
• Characteristic (Elliptic Integral)
• Characteristic Equation
• Characteristic (Euler)
• Characteristic Factor
• Characteristic (Field)