Pigeonhole Sort in C

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.

```
/*
```

 *  C Program to Implement Pigeonhole Sort

```
 */
```
```
#include <stdio.h>
```
```
 
```
```
#define MAX 7
```
```
 
```
```
void pigeonhole_sort(int, int, int *);
```
```
void main()
```
```
{
```
```
    int a[MAX], i, min, max;
```

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

```
    for (i = 0; i < MAX; i++)
```
```
    {
```
```
        scanf("%d", &a[i]);
```
```
    }
```
```
    min = a[0];
```
```
    max = a[0];
```
```
    for (i = 1; i < MAX; i++)
```
```
    {
```
```
        if (a[i] < min)
```
```
        {
```
```
            min = a[i];
```
```
        }
```
```
        if (a[i] > max)
```
```
        {
```
```
            max = a[i];
```
```
        }
```
```
    }
```
```
    pigeonhole_sort(min, max, a);
```
```
    printf("Sorted order is :\n");
```
```
    for (i = 0; i < MAX; i++)
```
```
    {
```
```
        printf("%d", a[i]);
```
```
    }
```
```
}
```
```
 
```

/* sorts the array using pigeonhole algorithm */

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

```
{
```
```
 
```
```
    int size, count = 0, i;
```
```
    int *current;
```
```
    current = a;
```
```
    size = ma - mi + 1;
```
```
    int holes[size];
```
```
    for (i = 0; i < size; i++)
```
```
    {
```
```
        holes[i] = 0;
```
```
    }
```

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

```
    {
```
```
        holes[*current-mi] += 1;
```
```
    }
```

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

```
    {
```
```
        while (holes[count]--> 0)
```
```
        {
```
```
            *current++ = count + mi;
```
```
        }
```
```
    }
```
```
}
```

 
$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.

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.

If you find any mistake above, kindly email to [email protected]

« Prev - C Program to Implement Qsort using Function Pointers

» Next - C Program to Implement Cyclesort

Related Posts:

Recommended Articles: