C Exercises: Sort numbers using Pigeonhole sort method

C Programming Searching and Sorting Algorithm: Exercise-20 with Solution

Write a C program that sorts numbers using the Pigeonhole sort method.

From Wikipedia:
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. It is similar to counting sort, but differs in that it "moves items twice: once to the bucket array and again to the final destination [whereas] counting sort builds an auxiliary array then uses the array to compute each item's final destination and move the item there.

The pigeonhole algorithm works as follows:
Given an array of values to be sorted, set up an auxiliary array of initially empty "pigeonholes", one pigeonhole for each key in the range of the keys in the original array.
Going over the original array, put each value into the pigeonhole corresponding to its key, such that each pigeonhole eventually contains a list of all values with that key.
Iterate over the pigeonhole array in increasing order of keys, and for each pigeonhole, put its elements into the original array in increasing order.

Sample Solution:

Sample C Code:

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

// Function to perform Pigeonhole Sort
int* pigeonholeSort(int arra_nums[], int size) {
    int i, j, min_val = arra_nums[0], max_val = arra_nums[0], range;

    // Find the minimum and maximum values in the array
    for (i = 1; i < size; i++) {
        if (arra_nums[i] < min_val)
            min_val = arra_nums[i];
        if (arra_nums[i] > max_val)
            max_val = arra_nums[i];
    }

    // Calculate the range of values
    range = max_val - min_val + 1;

    // Create an array to store counts of each element in the range
    int *temp = (int *)malloc(sizeof(int) * range);

    // Initialize the temp array with zeros
    for (i = 0; i < range; i++) {
        temp[i] = 0;
    }

    // Count the occurrences of each element in the input array
    for (i = 0; i < size; i++) {
        temp[arra_nums[i] - min_val]++;
    }

    j = 0;

    // Reconstruct the sorted array based on the counts
    for (i = 0; i < range; i++) {
        while (temp[i] > 0) {
            arra_nums[j] = i + min_val;
            temp[i]--;
            j++;
        }
    }

    return arra_nums;
}

// Main function
int main() {
    int arra_nums[100], i, n=0;    

    // Input the number of elements
    printf("Input number of elements you want to sort: ");
    scanf("%d", &n);

    // Check if there is at least one element
    if ( n >= 1) {
        printf("\nInput the numbers:\n");    

        // Input the array elements
        for (i = 0; i < n; i++)
            scanf(" %d", &arra_nums[i]);

        // Call the pigeonholeSort function to sort the array
        int* result_arra = pigeonholeSort(arra_nums, n);

        // Display the sorted array
        printf("Sorted array: \n");
        for (i = 0; i < n; i++) {
            printf("%d ", result_arra[i]);
        }
        printf("\n");
    }

    return 0;
}

Sample Output:

Input number of elements you want to sort: 5

Input the numbers:
10 11 12 13 14 15 16 17 18 19 20
Sorted array:
10 11 12 13 14

--------------------------------
Process exited after 25.3 seconds with return value 0
Press any key to continue . . .

Flowchart:

C Programming Code Editor:

Previous: Write a C program that sort numbers using Randomised quick sort method.
Next:Write a C program that sort numbers using partition sort method.