Pigeonhole Sort – Sorting Algorithm

Pigeonhole Sort

Pigeonhole Sort is an algorithm that sorts data by distributing elements into “pigeonholes” (buckets) based on their values. It is particularly effective when the range of data values is small and the data consists of integers.

---

1. Characteristics

1. Range-Based Sorting:
   • It works by placing elements into buckets corresponding to their values within a specific range (min to max).
2. Pigeonhole Principle:
   • Based on the mathematical principle that if n items are placed into mm containers, where n > m, at least one container must contain more than one item.
3. Constraints:
   • Efficient when the range of input values is small.
   • Input values should be integers or easily mapped to integers.
4. Stability:
   • The default implementation is not stable, but it can be modified for stability.

---

2. Working Mechanism

Steps:

1. Find Minimum and Maximum Values:
   • Determine the smallest (min) and largest (max) values in the array.
2. Create Pigeonholes:
   • Create an array of empty buckets, where the number of buckets equals the range (max − min + 1).
3. Distribute Elements:
   • Place each element from the input array into its corresponding bucket based on its value.
4. Collect Sorted Data:
   • Retrieve elements from the buckets in order, forming the sorted array.

---

3. Time and Space Complexity

• Time Complexity:
  • O(n + r), where n is the number of elements, and r is the range (max − min + 1).
• Space Complexity:
  • O(r), as additional space is needed to store the buckets.

---

4. Advantages and Disadvantages

Advantages:

1. Fast Execution:
   • Performs well for small ranges.
2. Simple Logic:
   • Easy to understand and implement.

Disadvantages:

1. High Space Usage:
   • Inefficient if the range is large.
2. Limited Applicability:
   • Works only for data with a narrow range or integer-based values.

---

5. Example Code

Java Implementation

import java.util.ArrayList;

public class PigeonholeSort {
    public static void pigeonholeSort(int[] arr) {
        int min = arr[0];
        int max = arr[0];
        int n = arr.length;

        // Find the minimum and maximum values
        for (int i = 1; i < n; i++) {
            if (arr[i] < min) {
                min = arr[i];
            }
            if (arr[i] > max) {
                max = arr[i];
            }
        }

        int range = max - min + 1; // Range of the values in the array
        ArrayList<Integer>[] pigeonholes = new ArrayList[range];

        // Initialize pigeonholes
        for (int i = 0; i < range; i++) {
            pigeonholes[i] = new ArrayList<>();
        }

        // Place elements into pigeonholes
        for (int num : arr) {
            pigeonholes[num - min].add(num);
        }

        // Collect sorted elements
        int index = 0;
        for (ArrayList<Integer> hole : pigeonholes) {
            for (int num : hole) {
                arr[index++] = num;
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = {8, 3, 2, 7, 4, 6, 8, 1, 9};
        System.out.println("Original Array:");
        for (int num : arr) {
            System.out.print(num + " ");
        }

        pigeonholeSort(arr);

        System.out.println("\nSorted Array:");
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

---

Python Implementation

def pigeonhole_sort(arr):
    # Find minimum and maximum values
    min_val = min(arr)
    max_val = max(arr)
    range_size = max_val - min_val + 1

    # Create pigeonholes
    pigeonholes = [[] for _ in range(range_size)]

    # Place elements into pigeonholes
    for num in arr:
        pigeonholes[num - min_val].append(num)

    # Collect sorted elements
    sorted_arr = []
    for hole in pigeonholes:
        sorted_arr.extend(hole)

    return sorted_arr


# Example usage
if __name__ == "__main__":
    arr = [8, 3, 2, 7, 4, 6, 8, 1, 9]
    print("Original Array:", arr)

    sorted_arr = pigeonhole_sort(arr)
    print("Sorted Array:", sorted_arr)

---

6. Example Execution

Input:

• Array: [8, 3, 2, 7, 4, 6, 8, 1, 9]

Steps:

1. Minimum value = 1, Maximum value = 9, Range size = 9.
2. Create buckets (empty arrays).
3. Distribute elements into corresponding buckets:
   • [1], [2], [3], [4], [6], [7], [8, 8], [9].
4. Collect sorted elements from buckets.

Output:

• [1, 2, 3, 4, 6, 7, 8, 8, 9]

---

7. Use Cases

1. Sorting Exam Scores:
   • Efficient for datasets like test scores with a limited range.
2. Categorization Tasks:
   • Effective for datasets where elements can be mapped to discrete ranges.

Pigeonhole Sort is a simple and efficient algorithm for specific scenarios involving narrow ranges and integer-based data.