Input and Output Assumptions
In the most general case, the input to counting sort consists of a collection of n items, each of which has a non-negative integer key whose maximum value is at most k. In some descriptions of counting sort, the input to be sorted is assumed to be more simply a sequence of integers itself, but this simplification does not accommodate many applications of counting sort. For instance, when used as a subroutine in radix sort, the keys for each call to counting sort are individual digits of larger item keys; it would not suffice to return only a sorted list of the key digits, separated from the items.
In applications such as in radix sort, a bound on the maximum key value k will be known in advance, and can be assumed to be part of the input to the algorithm. However, if the value of k is not already known then it may be computed by an additional loop over the data to determine the maximum key value that actually occurs within the data.
The output is an array of the items, in order by their keys. Because of the application to radix sorting, it is important for counting sort to be a stable sort: if two items have the same key as each other, they should have the same relative position in the output as they did in the input.
Read more about this topic: Counting Sort
Famous quotes containing the words input, output and/or assumptions:
“Celebrity is a mask that eats into the face. As soon as one is aware of being “somebody,” to be watched and listened to with extra interest, input ceases, and the performer goes blind and deaf in his overanimation. One can either see or be seen.”
—John Updike (b. 1932)
“Lizzie Borden took an axe
And gave her mother forty whacks;
When she saw what she had done,
She gave her father forty-one.”
—Anonymous. Late 19th century ballad.
The quatrain refers to the famous case of Lizzie Borden, tried for the murder of her father and stepmother on Aug. 4, 1892, in Fall River, Massachusetts. Though she was found innocent, there were many who contested the verdict, occasioning a prodigious output of articles and books, including, most recently, Frank Spiering’s Lizzie (1985)
“Unlike Boswell, whose Journals record a long and unrewarded search for a self, Johnson possessed a formidable one. His life in London—he arrived twenty-five years earlier than Boswell—turned out to be a long defense of the values of Augustan humanism against the pressures of other possibilities. In contrast to Boswell, Johnson possesses an identity not because he has gone in search of one, but because of his allegiance to a set of assumptions that he regards as objectively true.”
—Jeffrey Hart (b. 1930)