Home » C/C++ Data Structure Programs

C program to implement pigeonhole sort algorithm

Here, we are going to learn how to implement pigeonhole sort algorithm using C program?
Submitted by Nidhi, on August 16, 2021

Problem Solution:

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.

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.

Program:

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.