C Programming Code Examples

C > Sorting Searching Code Examples

C Program to Implement Pigeonhole Sort



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

    #include <stdio.h>

    #define MAX 7

    void pigeonhole_sort(int, int, int *);

    void main()

    {

        int a[MAX], j, min, max;

        printf("enter the values into the matrix :");

        for (j = 0; j < MAX; j++)

        {

            scanf("%d", &a[j]);

        }

        min = a[0];

        max = a[0];

        for (j = 1; j < MAX; j++)

        {

            if (a[j] < min)

            {

                min = a[j];

            }

            if (a[j] > max)

            {

                max = a[j];

            }

        }

        pigeonhole_sort(min, max, a);

        printf("Sorted order is :\n");

        for (j = 0; j < MAX; j++)

        {

            printf("%d", a[j]);

        }

    }

    /* sorts the array using pigeonhole algorithm */

    void pigeonhole_sort(int mx, int ma, int * a)

    {

        int size, count = 0, j;

        int *current;

        current = a;

        size = ma - mx + 1;

        int holes[size];

        for (j = 0; j < size; j++)

        {

            holes[j] = 0;

        }

        for (j = 0; j < size; j++, current++)

        {

            holes[*current-mx] += 1;

        }

        for (count = 0, current = &a[0]; count < size; count++)

        {

            while (holes[count]--> 0)

            {

                *current++ = count + mx;

            }

        }

    }