How To Do Pigeonhole Sort in JavaScript

Pigeonhole Sort is a distribution-based sorting algorithm that excels in specific scenarios. This post explains how Pigeonhole Sort works, implements it in JavaScript, and explores its efficiency and use cases. We’ll examine its time complexity, strengths, and limitations, helping you understand when to choose this algorithm.

What is Pigeonhole Sort?

Pigeonhole Sort is a sorting algorithm that distributes elements into a set of “pigeonholes” based on their values. Each pigeonhole corresponds to a single value. After distribution, the pigeonholes are processed in order, effectively sorting the elements.

The algorithm gets its name from the pigeonhole principle in mathematics, which states that if you have n items to put into m containers and n > m, at least one container must contain more than one item.

Pigeonhole Sort vs. Bucket Sort

While often confused, Pigeonhole Sort and Bucket Sort have key differences:

1. Distribution:
   • Pigeonhole Sort: Each pigeonhole corresponds to exactly one possible value.
   • Bucket Sort: Each bucket can contain a range of values.
2. Secondary sorting:
   • Pigeonhole Sort: No secondary sorting is needed within pigeonholes.
   • Bucket Sort: Requires sorting within each bucket.
3. Efficiency:
   • Pigeonhole Sort: More efficient when the range of possible values is close to the number of elements.
   • Bucket Sort: More versatile, especially for floating-point numbers or when the range is much larger than the number of elements.

Pseudocode for Pigeonhole Sort

Here’s a high-level pseudocode for Pigeonhole Sort:

function pigeonholeSort(array):
    min = findMinimum(array)
    max = findMaximum(array)
    range = max - min + 1

    // Create pigeonholes
    pigeonholes = new array of size 'range', initialized with empty arrays

    // Distribute elements into pigeonholes
    for each element in array:
        pigeonholeIndex = element - min
        add element to pigeonholes[pigeonholeIndex]

    // Collect elements from pigeonholes
    index = 0
    for each pigeonhole in pigeonholes:
        for each element in pigeonhole:
            array[index] = element
            index = index + 1

    return array

Time and Space Complexity for Pigeonhole Sort

• Time Complexity:
  • Best case: O(n + range)
  • Average case: O(n + range)
  • Worst case: O(n + range)
• Space Complexity: O(n + range)

Where n is the number of elements in the array and range is the difference between the maximum and minimum values plus one.

JavaScript Implementation of Pigeonhole Sort

Here is the implementation for Pigeonhole Sort in JavaScript.

function pigeonholeSort(arr) {
    if (arr.length === 0) return arr;

    // Find minimum and maximum values
    let min = arr[0];
    let max = arr[0];
    for (let i = 1; i < arr.length; i++) {
        if (arr[i] < min) min = arr[i];
        if (arr[i] > max) max = arr[i];
    }

    const range = max - min + 1;

    // Create pigeonholes
    const pigeonholes = new Array(range).fill().map(() => []);

    // Distribute elements into pigeonholes
    for (let i = 0; i < arr.length; i++) {
        pigeonholes[arr[i] - min].push(arr[i]);
    }

    // Collect elements from pigeonholes
    let index = 0;
    for (let i = 0; i < range; i++) {
        while (pigeonholes[i].length > 0) {
            arr[index++] = pigeonholes[i].pop();
        }
    }

    return arr;
}

// Example usage
const arr = [8, 3, 2, 7, 4, 6, 8];
console.log("Original array:", arr);
pigeonholeSort(arr);
console.log("Sorted array:", arr);

Output:

Original array: [
  8, 3, 2, 7,
  4, 6, 8
]
Sorted array: [
  2, 3, 4, 6,
  7, 8, 8
]

Walk Through of the Example

Let’s walk through how Pigeonhole Sort would sort the array [8, 3, 2, 7, 4, 6, 8]:

1. Find min (2) and max (8). The range is 8 - 2 + 1 = 7.
2. Create 7 pigeonholes, indexed 0 to 6.
3. Distribute elements:
   • 8 goes to pigeonhole 6 (8 – 2 = 6)
   • 3 goes to pigeonhole 1 (3 – 2 = 1)
   • 2 goes to pigeonhole 0 (2 – 2 = 0)
   • 7 goes to pigeonhole 5 (7 – 2 = 5)
   • 4 goes to pigeonhole 2 (4 – 2 = 2)
   • 6 goes to pigeonhole 4 (6 – 2 = 4)
   • 8 goes to pigeonhole 6 (8 – 2 = 6)
4. Collect elements from pigeonholes in order:
   • [2, 3, 4, 6, 7, 8, 8]
5. The array is now sorted.

Pros and Cons of Pigeonhole Sort

Pros:

1. Very efficient for sorting integers with a known, limited range.
2. Simple to implement and understand.
3. Stable sort (maintains relative order of equal elements).
4. It can be faster than comparison-based sorts for certain data distributions.

Cons:

1. Requires additional memory proportional to the range of input.
2. Not efficient for large ranges relative to the number of elements.
3. Not suitable for floating-point numbers or non-numeric data without modification.
4. Performance degrades with non-uniform distributions.

When to Use Pigeonhole Sort

Pigeonhole Sort is most effective in the following scenarios:

1. When sorting integers with a known, limited range.
2. When the range of possible values is not significantly larger than the number of elements to be sorted.
3. When dealing with uniformly distributed data within the given range.
4. In situations where stability (preserving the relative order of equal elements) is essential.

Conclusion

Pigeonhole Sort offers a unique approach to sorting that can be highly efficient in specific scenarios. Its linear time complexity makes sorting integers with a limited range attractive. However, its performance and space requirements can degrade quickly as the range of values increases relative to the number of elements.

While not as versatile as comparison-based sorts like Quick Sort or Merge Sort, Pigeonhole Sort reminds us that sometimes, with the right data characteristics, simpler algorithms can outperform more complex ones.

Congratulations on reading to the end of this tutorial!

Read the following articles to learn how to implement Pigeonhole Sort:

In Python – How to do Pigeonhole Sort in Python

In C++ – How To Do Pigeonhole Sort in C++

Have fun and happy researching!