DEV Community

Dumb Down Demistifying Dev
Dumb Down Demistifying Dev

Posted on

Pigeonhole Sort

What do we understand about Pigeonhole Sort?

  • Very very very simple and straightforward sorting algorithm
  • One of the most effecient sorting algorithm with JS implementation to be as fast as 1 digit millisecond
  • Is NOT a comparison sort
  • ONLY Interger values from negative to positive
  • Stable algorithm
  • Handles sorting by placing integer value by index of new Array
  • The new Array's index holds an Array of the copied integer value when interated over
  • In JS can be done in ONE loop
  • Returns a new Array
  • Time complexity
    • Best is O(n+k)
    • Average is O(n+k)
    • Worst is O(n+k)
  • Space complexity
    • O(n+k)
  • Note: n – Size of array, k - Range of value
function PigeonHoleSort(arr) {
  const min = Math.min(...arr);
  const pigeonhole = [];

  arr.forEach(num => {
    if (pigeonhole[num - min]) pigeonhole[num - min].push(num);
    else pigeonhole[num - min] = [num];
  });
  return pigeonhole.flat();
}
Enter fullscreen mode Exit fullscreen mode

Top comments (0)