{"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":"
\n

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

\n

It requires O(n<\/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

Working of Algorithm :<\/strong><\/p>\n

    \n
  1. 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
  2. Set up an array of initially empty \u201cpigeonholes\u201d the same size as of the range.<\/li>\n
  3. 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
  4. 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=”banner”]\n

    Comparison with Counting Sort : <\/strong>
    \nIt is similar to 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

    Below is C++ implementation of Pegionhole Sort.<\/strong><\/p>\n

    c++<\/span> <\/div> 
    \/* C program to implement Pegionhole Sort *\/#include <bits\/stdc++.h>using namespace std; \/* Sorts the array using pigeonhole algorithm *\/void pigeonholeSort(int arr[], int n){    \/\/ Find minimum and maximum values in arr[]    int min = arr[0], max = arr[0];    for (int i = 1; i < n; i++)    {        if (arr[i] < min)            min = arr[i];        if (arr[i] > max)            max = arr[i];    }    int range = max - min + 1; \/\/ Find range     \/\/ Create an array of vectors. Size of array    \/\/ range. Each vector represents a hole that    \/\/ is going to contain matching elements.    vector<int> holes[range];     \/\/ Traverse through input array and put every    \/\/ element in its respective hole    for (int i = 0; i < n; i++)        holes[arr[i]-min].push_back(arr[i]);     \/\/ Traverse through all holes one by one. For    \/\/ every hole, take its elements and put in    \/\/ array.    int index = 0;  \/\/ index in sorted array    for (int i = 0; i < range; i++)    {       vector<int>::iterator it;       for (it = holes[i].begin(); it != holes[i].end(); ++it)            arr[index++]  = *it;    }} \/\/ Driver program to test the above functionint main(){    int arr[] = {8, 3, 2, 7, 4, 6, 8};    int n = sizeof(arr)\/sizeof(arr[0]);     pigeonholeSort(arr, n);     printf("Sorted order is : ");    for (int i = 0; i < n; i++)        printf("%d ", arr[i]);     return 0;}<\/code><\/pre> <\/div>\n
    Output:<\/strong><\/p>\n
    Sorted order is : 2 3 4 6 7 8 8<\/pre>\n
    Pigeonhole sort has limited use as requirements are rarely met. For arrays where range is much larger than n<\/em>, bucket sort is a generalization that is more efficient in space and time.<\/p>\n[ad type=”banner”]\n<\/div>\n","protected":false},"excerpt":{"rendered":"
    Pigeonhole sort – Searching and sorting – 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}]}}