{"id":25213,"date":"2017-10-15T15:40:14","date_gmt":"2017-10-15T10:10:14","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=25213"},"modified":"2017-10-15T15:40:14","modified_gmt":"2017-10-15T10:10:14","slug":"pigeonhole-sort","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/pigeonhole-sort\/","title":{"rendered":"Pigeonhole Sort"},"content":{"rendered":"<header class=\"entry-header\">\n<p class=\"entry-title\">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.<\/p>\n<\/header>\n<div class=\"entry-content\">\n<p>It requires O(<i>n<\/i> + <i>Range<\/i>) time where n is number of elements in input array and \u2018Range\u2019 is number of possible values in array.<\/p>\n<p><strong>Working of Algorithm :<\/strong><\/p>\n<ol>\n<li>Find minimum and maximum values in array. Let the minimum and maximum values be \u2018min\u2019 and \u2018max\u2019 respectively. Also find range as \u2018max-min-1\u2019.<\/li>\n<li>Set up an array of initially empty \u201cpigeonholes\u201d the same size as of the range.<\/li>\n<li>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] \u2013 min.<\/li>\n<li>Start the loop all over the pigeonhole array in order and put the elements from non- empty holes back into the original array.<\/li>\n<\/ol>\n[ad type=\u201dbanner\u201d]\n<p><strong>Comparison with Counting Sort : <\/strong><br \/>\nIt is similar to <a href=\"http:\/\/www.geeksforgeeks.org\/counting-sort\/\">counting sort<\/a>, but differs in that it \u201cmoves items twice: once to the bucket array and again to the final destination \u201c<\/p>\n<p><strong>Below is C++ implementation of Pegionhole Sort.<\/strong><\/p>\n[pastacode lang=\u201dcpp\u201d manual=\u201d%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\u201d message=\u201dc++\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n<p><strong>Output:<\/strong><\/p>\n<pre>Sorted order is : 2 3 4 6 7 8 8<\/pre>\n<p>Pigeonhole sort has limited use as requirements are rarely met. For arrays where range is much larger than <em>n<\/em>, bucket sort is a generalization that is more efficient in space and time.<\/p>\n[ad type=\u201dbanner\u201d]\n<\/div>\n","protected":false},"excerpt":{"rendered":"<p>Pigeonhole sort &#8211; Searching and sorting &#8211; 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<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[69969,83507,71670],"tags":[71852,72150,71832,71840,72143,72156,72157,72141,71121,71134,72163,70465,71151,71860,71855,72170,72147,72169,72162,71833,71146,71891,71868,72152,72153,72155,72133,72135,71989,72168,72136,72159,72131,72139,71875,72161,72151,70969,72164,72165,70075,71262,71276,72171,72154,72142,72166,71712,71677,72144,71266,71870,71857,71880,71867,71842,70016,72145,72140,70964,72158,72149,72167,72146,72134,72132,71125,72138,71161,70967,71887,72160,72148,72137],"class_list":["post-25213","post","type-post","status-publish","format-standard","hentry","category-algorithm","category-pigeonhole-sort","category-searching-and-sorting","tag-algorithm-for-radix-sort","tag-algorithm-interview-questions","tag-algorithm-of-bucket-sort","tag-algorithm-of-radix-sort","tag-algorithm-questions","tag-automatic-reply-example","tag-automatic-reply-sample","tag-bidirectional-bubble-sort","tag-bubble-sort-algorithm","tag-bubble-sort-algorithm-with-example","tag-bubble-sort-wiki","tag-bucket-sort","tag-bucket-sort-algorithm","tag-bucket-sort-algorithm-example","tag-bucket-sort-algorithm-with-example","tag-bucket-sort-c-program","tag-bucket-sort-program-in-c","tag-c-visualization","tag-cocktail-shaker-sort","tag-comb-sort","tag-comparison-of-sorting-algorithms","tag-counting-algorithm","tag-counting-sort-algorithm","tag-counting-sort-in-c","tag-counting-sort-program-in-c","tag-countingsort","tag-cycle-sort","tag-cycle-sort-algorithm","tag-different-sorting-algorithms-in-java","tag-different-types-of-sorting-algorithms","tag-discard-email","tag-envelope-example","tag-envelope-folder","tag-envelope-heading","tag-example-of-counting-sort","tag-gnome-sort","tag-how-to-sort-an-array-in-javascript","tag-java-sorting-algorithms","tag-javascript-sort-array-of-numbers","tag-javascript-sort-numbers","tag-linear-sort","tag-merge-sort-algorithm","tag-merge-sort-algorithm-with-example","tag-pigeonhole-principle-discrete-math","tag-pigeonhole-principle-in-discrete-mathematics","tag-pigeonhole-sort","tag-quick-sort-wiki","tag-quicksort-algorithm-with-example","tag-quicksort-explained","tag-quicksort-visualization","tag-radix-sort-algorithm","tag-radix-sort-algorithm-in-data-structure","tag-radix-sort-algorithm-pseudocode","tag-radix-sort-in-c","tag-radix-sort-program-in-c","tag-radix-sort-python","tag-selection-sort-algorithm","tag-selection-sort-algorithm-with-example","tag-selection-sort-algorithm-with-example-in-data-structure","tag-selection-sort-code","tag-selection-sort-python","tag-shaker-sort-algorithm","tag-shell-sort-animation","tag-shuttle-sort","tag-sieve-filter","tag-sieve-set","tag-sort-code","tag-sort-dictionary","tag-sorting-algorithms-comparison","tag-sorting-algorithms-java","tag-sorting-by-counting","tag-spam-examples","tag-time-and-space-complexity-of-algorithms-in-data-structure","tag-x-spam-score"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/25213","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/comments?post=25213"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/25213\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=25213"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=25213"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=25213"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}