Pigeonhole sorting is a sorting algorithm that is suitable for sorting lists of elements where the number of elements and the number of possible key values are approximately the same.
It requires O(n + Range) time where n is number of elements in input array and ‘Range’ is number of possible values in array.
Working of Algorithm :
- Find minimum and maximum values in array. Let the minimum and maximum values be ‘min’ and ‘max’ respectively. Also find range as ‘max-min-1’.
- Set up an array of initially empty “pigeonholes” the same size as of the range.
- Visit each element of the array and then put each element in its pigeonhole. An element arr[i] is put in hole at index arr[i] – min.
- Start the loop all over the pigeonhole array in order and put the elements from non- empty holes back into the original array.
Comparison with Counting Sort :
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 “
Below is C++ implementation of Pegionhole Sort.
[pastacode lang=”cpp” manual=”%2F*%20C%20program%20to%20implement%20Pegionhole%20Sort%20*%2F%0A%23include%20%3Cbits%2Fstdc%2B%2B.h%3E%0Ausing%20namespace%20std%3B%0A%20%0A%2F*%20Sorts%20the%20array%20using%20pigeonhole%20algorithm%20*%2F%0Avoid%20pigeonholeSort(int%20arr%5B%5D%2C%20int%20n)%0A%7B%0A%20%20%20%20%2F%2F%20Find%20minimum%20and%20maximum%20values%20in%20arr%5B%5D%0A%20%20%20%20int%20min%20%3D%20arr%5B0%5D%2C%20max%20%3D%20arr%5B0%5D%3B%0A%20%20%20%20for%20(int%20i%20%3D%201%3B%20i%20%3C%20n%3B%20i%2B%2B)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20if%20(arr%5Bi%5D%20%3C%20min)%0A%20%20%20%20%20%20%20%20%20%20%20%20min%20%3D%20arr%5Bi%5D%3B%0A%20%20%20%20%20%20%20%20if%20(arr%5Bi%5D%20%3E%20max)%0A%20%20%20%20%20%20%20%20%20%20%20%20max%20%3D%20arr%5Bi%5D%3B%0A%20%20%20%20%7D%0A%20%20%20%20int%20range%20%3D%20max%20-%20min%20%2B%201%3B%20%2F%2F%20Find%20range%0A%20%0A%20%20%20%20%2F%2F%20Create%20an%20array%20of%20vectors.%20Size%20of%20array%0A%20%20%20%20%2F%2F%20range.%20Each%20vector%20represents%20a%20hole%20that%0A%20%20%20%20%2F%2F%20is%20going%20to%20contain%20matching%20elements.%0A%20%20%20%20vector%3Cint%3E%20holes%5Brange%5D%3B%0A%20%0A%20%20%20%20%2F%2F%20Traverse%20through%20input%20array%20and%20put%20every%0A%20%20%20%20%2F%2F%20element%20in%20its%20respective%20hole%0A%20%20%20%20for%20(int%20i%20%3D%200%3B%20i%20%3C%20n%3B%20i%2B%2B)%0A%20%20%20%20%20%20%20%20holes%5Barr%5Bi%5D-min%5D.push_back(arr%5Bi%5D)%3B%0A%20%0A%20%20%20%20%2F%2F%20Traverse%20through%20all%20holes%20one%20by%20one.%20For%0A%20%20%20%20%2F%2F%20every%20hole%2C%20take%20its%20elements%20and%20put%20in%0A%20%20%20%20%2F%2F%20array.%0A%20%20%20%20int%20index%20%3D%200%3B%20%20%2F%2F%20index%20in%20sorted%20array%0A%20%20%20%20for%20(int%20i%20%3D%200%3B%20i%20%3C%20range%3B%20i%2B%2B)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20vector%3Cint%3E%3A%3Aiterator%20it%3B%0A%20%20%20%20%20%20%20for%20(it%20%3D%20holes%5Bi%5D.begin()%3B%20it%20!%3D%20holes%5Bi%5D.end()%3B%20%2B%2Bit)%0A%20%20%20%20%20%20%20%20%20%20%20%20arr%5Bindex%2B%2B%5D%20%20%3D%20*it%3B%0A%20%20%20%20%7D%0A%7D%0A%20%0A%2F%2F%20Driver%20program%20to%20test%20the%20above%20function%0Aint%20main()%0A%7B%0A%20%20%20%20int%20arr%5B%5D%20%3D%20%7B8%2C%203%2C%202%2C%207%2C%204%2C%206%2C%208%7D%3B%0A%20%20%20%20int%20n%20%3D%20sizeof(arr)%2Fsizeof(arr%5B0%5D)%3B%0A%20%0A%20%20%20%20pigeonholeSort(arr%2C%20n)%3B%0A%20%0A%20%20%20%20printf(%22Sorted%20order%20is%20%3A%20%22)%3B%0A%20%20%20%20for%20(int%20i%20%3D%200%3B%20i%20%3C%20n%3B%20i%2B%2B)%0A%20%20%20%20%20%20%20%20printf(%22%25d%20%22%2C%20arr%5Bi%5D)%3B%0A%20%0A%20%20%20%20return%200%3B%0A%7D” message=”c++” highlight=”” provider=”manual”/]Output:
Sorted order is : 2 3 4 6 7 8 8
Pigeonhole sort has limited use as requirements are rarely met. For arrays where range is much larger than n, bucket sort is a generalization that is more efficient in space and time.
[ad type=”banner”]