Student Center | Instructor's Center | Introduction to Algorithms | Home

Introduction to Algorithms, 2/e

Thomas H. Cormen, Dartmouth College
Charles E. Leiserson, Massachusetts Institute of Technology
Ronald L. Rivest, Massachusetts Institute of Technology
Clifford Stein, Columbia University

Quicksort

Glossary

tail recursion	A method used with Quicksort which avoids the second recursive call by using an iterative control structure. (See page 162)



stack	Compilers usually execute recursive procedures by using a stack that contains pertinent information, including the parameter values, for each recursive call. (See page 162)



push	When a procedure is invoked, its information is pushed onto the stack. (See page 162)



pop	When a procedure terminates, its information is popped from the stack. (See page 162)



stack depth	the maximum amount of stack space used at any time during a computation (See page 162)



median-of-3	One way to improve the RANDOMIZED-QUICKSORT procedure is to partition around a pivot that is chosen more carefully than by picking a random element from the subarray. One common approach is the median-of-3 method: choose the pivot as the median (middle element) of a set of 3 elements randomly selected from the subarray. (See page 162)



fuzzy sorting of intervals	Consider a sorting problem in which the numbers are not known exactly. Instead, for each number, we know an interval on the real line to which it belongs. That is, we are given n closed intervals of the form [a_i, b_i], where a_i ≤ b_i. The goal is to fuzzy-sort these intervals, i.e., produce a permutation (i₁, i₂,...,i_n) of the intervals such that there exist c_j ∈ [a_{i_j}, b_{i_j}] satisfying c₁ ≤ c₂ ≤ · · · ≤ c_n. (See page 163)

2002 McGraw-Hill Higher Education
Any use is subject to the Terms of Use and Privacy Policy.
McGraw-Hill Higher Education is one of the many fine businesses of The McGraw-Hill Companies.