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();
}
Top comments (0)