Index: > A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

Home > Pigeonhole sort

Pigeonhole sorting takes linear time ( O(n)), which is the best possible performance for a sort algorithm since one must inevitably look at each of the elements being sorted at least once, regardless of the sorting algorithm. However, it requires

that no two objects in the array be identical;
an invertible function mapping the objects you are sorting to integers within a small range (say, 0 to 1000).

The range must be limited to some constant times the number of elements that is being sorted to achieve the linear running time. Pigeonhole sort orders the elements by the result of this mapping.

The algorithm works as follows.

Set up an array of initially empty "pigeonholes" the size of the range.
Go over the original array, putting each object in its pigeonhole.
Iterate over the pigeonhole array in order, and put elements from non-empty holes back into the original array.

The hidden constant for this algorithm depends critically on the density of the elements in the pigeonhole array. If there are many more array elements than items to be sorted, steps 1 and 3 will be relatively slow.

Pigeonhole sort is rarely used as the requirements are rarely met and other, more flexible, and almost as fast, sorting algorithms are easier to use. In particular, the bucket sort is a more practical variation on the pigeonhole sort.

Sample C99 code for this algorithm:

void pigeonhole_sort(int *low, int *high, int min, int max) { int count, *current; const int size = max - min + 1; bool holes[size]; /* Populate the pigeonholes. */ for (current = low; current <= high; current++) holes[*current - min] = true; /* Put the elements back into the array in order. */ for (current = low, count = 0; count < size; count++) if (holes[count]) *current++ = count + min; }

Note that min and max could also easily be determined within the function.

Sort algorithms

Politics	Business	Finance

Topics: Pigeonhole Sort Array Elements Algorithm Int Count Sorting Min...

Pigeonhole sortPigeonhole sorting takes linear time ( O n ), which is the best possible performance for a sort algorithm since one must inevitably look at each of the elements being sorted at least once, regardless of the sorting algorithm. However, it requires that no

Pigeonhole principleCombinatorics The pigeonhole principle states that if n pigeons are put into m pigeonholes, and if n > m then at least one pigeonhole must contain more than one pigeon. Another way of stating this would be that m holes can hold at most m objects with one

PigeonholeLiterally, a pigeonhole is a small hole in a loft, the nesting-place of a pigeon. This has led to two metaphorical uses: The term pigeonholing is used to describe processes which attempt to classify disparate entities into a small number of mutually exclu

Non User