This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed. Find sources: "Pigeonhole sort" – news · newspapers · books · scholar · JSTOR(July 2017) (Learn how and when to remove this message)
Pigeonhole sort
Class
Sorting algorithm
Data structure
Array
Worst-case performance
, where N is the range of key values and n is the input size
Worst-case space complexity
Optimal
If and only if
Pigeonhole sorting is a sorting algorithm that is suitable for sorting lists of elements where the number n of elements and the length N of the range of possible key values are approximately the same.[1] It requires O(n + N) time. It is similar to counting sort, but differs in that it "moves items twice: once to the bucket array and again to the final destination [whereas] counting sort builds an auxiliary array then uses the array to compute each item's final destination and move the item there."[2]
The pigeonhole algorithm works as follows:
Given an array of values to be sorted, set up an auxiliary array of initially empty "pigeonholes", one pigeonhole for each key in the range of the keys in the original array.
Going over the original array, put each value into the pigeonhole corresponding to its key, such that each pigeonhole eventually contains a list of all values with that key.
Iterate over the pigeonhole array in increasing order of keys, and for each pigeonhole, put its elements into the original array in increasing order.
^"NIST's Dictionary of Algorithms and Data Structures: pigeonhole sort".
^Black, Paul E. "Dictionary of Algorithms and Data Structures". NIST. Retrieved 6 November 2015.
Pigeonholesorting is a sorting algorithm that is suitable for sorting lists of elements where the number n of elements and the length N of the range of...
a pigeon coop Pigeonholing, classifying things into categories Pigeonhole principle, a mathematical principle Pigeonholesort, a sorting algorithm Pigeon-hole...
different sorting algorithm, or by recursively applying the bucket sorting algorithm. It is a distribution sort, a generalization of pigeonholesort that allows...
In computer science, a sorting algorithm is an algorithm that puts elements of a list into an order. The most frequently used orders are numerical order...
Pigeonholing is a process that attempts to classify disparate entities into a limited number of categories (usually, mutually exclusive ones). The term...
In mathematics, the pigeonhole principle states that if n items are put into m containers, with n > m, then at least one container must contain more than...
sorted are. Integer sorting algorithms including pigeonholesort, counting sort, and radix sort are widely used and practical. Other integer sorting algorithms...
sort is implemented without a mechanism to assist in finding empty spaces below the beads, such as in software implementations. Like the Pigeonhole sort...
The bucket queue is the priority-queue analogue of pigeonholesort (also called bucket sort), a sorting algorithm that places elements into buckets indexed...
tray of every desk and also the internal mail pigeonhole of every department The post room worker sorts the mail by department using the wallets on his...
Guardian observed her ability to not be pigeonholed into a type of role, and wrote that she "specialises in a sort of calculated understatement", praising...
using auxiliary data structures to track violations, and applying the pigeonhole principle. Strict Fibonacci heaps were invented in 2012 by Gerth S. Brodal...
of any sort." He considers "nothing more addictive than the sound of an audience laughing" and, regarding the possibility of being "pigeonholed" as a children's...
polished stone samples, doubtless marbles and jaspers or fitted with pigeonhole compartments for specimens. Below them, a range of cupboards contain specimen...
context of political theory. The term heresy is also used as an ideological pigeonhole for contemporary writers because, by definition, heresy depends on contrasts...
folders are then sorted by taxonomic family according to the standard system selected for use by the herbarium and placed into pigeonholes in herbarium cabinets...
member Pat Noel said many bands were dismayed at how journalists would "pigeonhole" them to the collective. "We kind of made a conscious decision to distance...
got Howard thinking about how the other Star Trek actors had become pigeonholed in these roles since the cancellation of Star Trek, and he then came...
range, which is perhaps surprising considering she has been thus far pigeonholed into more lightweight parts", and Colin Covert of the Star Tribune, who...
demeaning to 'secondaries' and 'tertiaries', or as an undesirable form of pigeonholing, and so prefer not to classify their relationships in this way. Among...
as synthesized, manufactured pop only remotely resembling punk, and pigeonholed as a joke act due to the puerile slant of its singles and associating...
folders are then sorted by taxonomic family according to the standard system selected for use by the herbarium and placed into pigeonholes in herbarium cabinets...
there are ( n + 1 ) {\displaystyle (n+1)} 'a's and only n states by the pigeonhole principle. Call this state S, and further let d be the number of 'a's...
television audience knows we're a diverse tribe, not easily pigeonholed. Modern Family endows us with a sort of comic banality. It's an odd kind of progress. But...
Global Information
