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)

This post blew up on DEV in 2020:

js visualized

🚀⚙️ JavaScript Visualized: the JavaScript Engine

As JavaScript devs, we usually don't have to deal with compilers ourselves. However, it's definitely good to know the basics of the JavaScript engine and see how it handles our human-friendly JS code, and turns it into something machines understand! 🥳

Happy coding!