 |  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
Sorting in Linear Time
Glossary
| comparison sorts | algorithms in which the sorted order they determine is based only on comparisons between the input elements.
(See page 165)
| | | | | decision tree | a full binary tree that represents the comparisons between elements that are performed by a particular sorting algorithm operating on an input of a given size. Control, data movement, and all other aspects of the algorithm are ignored.
(See page 166)
| | | | | counting sort | assumes that each of the n input elements is an integer in the range 0 to k, for some integer k. The basic idea is to determine, for each input element x, the number of elements less than x. This information can be used to place element x directly into its position in the output array.
(See page 168)
| | | | | stable | An important property of counting sort in that numbers with the same value appear in the output array in the same order as they do in the input array.
(See page 170)
| | | | | Radix sort | the algorithm used by the card-sorting machines you now find only in computer museums. The cards are organized into 80 columns, and in each column a hole can be punched in one of 12 places. The sorter can be mechanically "programmed" to examine a given column of each card in a deck and distribute the card into one of 12 bins depending on which place has been punched. An operator can then gather the cards bin by bin, so that cards with the first place punched are on top of cards with the second place punched, and so on.
(See page 170)
| | | | | bucket sort | sorts by dividing the interval [0, 1) into n equal-sized subintervals, or buckets, and then distributes the n input numbers into the buckets.
(See page 174)
|
|
2002 McGraw-Hill Higher Education