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:
“Family life is not a computer program that runs on its own; it needs continual input from everyone.”
—Neil Kurshan (20th century)
“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)
“Why did he think adding meant increase?
To me it was dilution. Where do these
Innate assumptions come from?”
—Philip Larkin (1922–1986)