C Program to Implement Pigeonhole Sort

«
»
This C Program implement pigeonhole sort. Pigeonhole sorting, also known as count sort, is a sorting algorithm that is suitable for sorting lists of elements where the number of elements (n) and the number of possible key values (N) are approximately the same.[1] It requires O(n + N) time

Here is source code of the C Program to implement pigeonhole sort. The C program is successfully compiled and run on a Linux system. The program output is also shown below.

  1. /*
  2.  *  C Program to Implement Pigeonhole Sort
  3.  */
  4. #include <stdio.h>
  5.  
  6. #define MAX 7
  7.  
  8. void pigeonhole_sort(int, int, int *);
  9. void main()
  10. {
  11.     int a[MAX], i, min, max;
  12.     printf("enter the values into the matrix :");
  13.     for (i = 0; i < MAX; i++)
  14.     {
  15.         scanf("%d", &a[i]);
  16.     }
  17.     min = a[0];
  18.     max = a[0];
  19.     for (i = 1; i < MAX; i++)
  20.     {
  21.         if (a[i] < min)
  22.         {
  23.             min = a[i];
  24.         }
  25.         if (a[i] > max)
  26.         {
  27.             max = a[i];
  28.         }
  29.     }
  30.     pigeonhole_sort(min, max, a);
  31.     printf("Sorted order is :\n");
  32.     for (i = 0; i < MAX; i++)
  33.     {
  34.         printf("%d", a[i]);
  35.     }
  36. }
  37.  
  38. /* sorts the array using pigeonhole algorithm */
  39. void pigeonhole_sort(int mi, int ma, int * a)
  40. {
  41.  
  42.     int size, count = 0, i;
  43.     int *current;
  44.     current = a;
  45.     size = ma - mi + 1;
  46.     int holes[size];
  47.     for (i = 0; i < size; i++)
  48.     {
  49.         holes[i] = 0;
  50.     }
  51.     for (i = 0; i < size; i++, current++)
  52.     {
  53.         holes[*current-mi] += 1;
  54.     }
  55.     for (count = 0, current = &a[0]; count < size; count++)
  56.     {
  57.         while (holes[count]--> 0)
  58.         {
  59.             *current++ = count + mi;
  60.         }
  61.     }
  62. }

 
$cc pigeonholesort.c
 
/* average case */
$ a.out
enter the values into the matrix :7 3 8 2 5 4 9
Sorted order is :
2345789
 
/* best case */
$ a.out
enter the values into the matrix :1 2 3 4 5 6 7
Sorted order is :
1234567
 
/* worst case */
$ a.out
enter the values into the matrix :7 6 5 4 3 2 1
Sorted order is :
1234567

Sanfoundry Global Education & Learning Series – 1000 C Programs.

Note: Join free Sanfoundry classes at Telegram or Youtube
advertisement
advertisement

Here’s the list of Best Books in C Programming, Data-Structures and Algorithms

If you wish to look at programming examples on all topics, go to C Programming Examples.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & technical discussions at Telegram SanfoundryClasses.