C program to implement pigeonhole sort algorithm

Pigeonhole sort algorithm: In this tutorial, we will learn how to implement pigeonhole sort algorithm using the C program? By Nidhi Last updated : August 03, 2023

Pigeonhole Sort Algorithm

Pigeonhole sorting is a sorting algorithm that is suitable for sorting lists of elements where the number of elements (n) and the length of the range of possible key values (N) are approximately the same. It requires O(n + N) time. Read more at Wikipedia.

Problem statement

Here, we will create an array of integers then we will read array elements from the user and implement a pigeonhole sort algorithm to arrange array elements in ascending order.

C program to implement pigeonhole sort algorithm

The source code to implement the pigeonhole sort algorithm is given below. The given program is compiled and executed using GCC compile on UBUNTU 18.04 OS successfully.

// C program to implement
// pigeonhole sort algorithm

#include <stdio.h>
#include <stdlib.h>

void pigeonHoleSort(int* arr, int len)
{
    int i = 0;
    int j = 0;
    int min = 0;
    int max = 0;
    int range = 0;

    int* temp;

    min = arr[0];
    max = arr[0];

    i = 1;
    while (i < len) {
        if (arr[i] < min)
            min = arr[i];
        if (arr[i] > max)
            max = arr[i];
        i++;
    }

    range = max - min + 1;
    temp = (int*)malloc(sizeof(int) * range);

    i = 0;
    while (i < range) {
        temp[i] = 0;
        i++;
    }

    i = 0;
    while (i < len) {
        temp[arr[i] - min]++;
        i++;
    }

    j = 0;
    i = 0;
    while (i < range) {
        while (temp[i] > 0) {
            arr[j] = i + min;
            temp[i]--;
            j++;
        }
        i++;
    }
}

int main()
{
    int arr[32] = { 0 };
    int i = 0;
    int n = 0;

    printf("Enter the size of array: ");
    scanf("%d", &n);

    printf("Enter Array elements:\n");
    for (i = 0; i < n; i++) {
        printf("Enter Arr[%d]: ", i);
        scanf(" %d", &arr[i]);
    }

    pigeonHoleSort(arr, n);

    printf("Sorted array: \n");
    for (i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    return 0;
}

Output

RUN 1:
Enter the size of array: 5
Enter Array elements:
Enter Arr[0]: 7
Enter Arr[1]: 5
Enter Arr[2]: 3
Enter Arr[3]: 10
Enter Arr[4]: 2
Sorted array: 
2 3 5 7 10

RUN 2:
Enter the size of array: 10
Enter Array elements:
Enter Arr[0]: 12
Enter Arr[1]: 23
Enter Arr[2]: 34
Enter Arr[3]: 45
Enter Arr[4]: 65
Enter Arr[5]: 10
Enter Arr[6]: 5
Enter Arr[7]: 2
Enter Arr[8]: 12
Enter Arr[9]: 1
Sorted array: 
1 2 5 10 12 12 23 34 45 65

Explanation

Here, we created two functions pigeonHoleSort() and main(). The pigeonHoleSort() is used to arrange array elements in ascending order.

In the main() function, we created an array of integers arr with 7 elements. Then we sorted the elements using the pigeonHoleSort() function and printed the sorted array on the console screen.