add pigeonhole sort · wxpython/algorithms@82500ba · GitHub
Skip to content

Commit 82500ba

Browse files
author
Liam
committed
add pigeonhole sort
1 parent 20c1c4e commit 82500ba

3 files changed

Lines changed: 34 additions & 0 deletions

File tree

‎README.md‎

Lines changed: 1 addition & 0 deletions

‎algorithms/sort/pigeonhole_sort.py‎

Lines changed: 28 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,28 @@
1+
"""
2+
3+
https://en.wikipedia.org/wiki/Pigeonhole_sort
4+
5+
Time complexity: O(n + Range) where n = number of elements and Range = possible values in the array
6+
7+
Suitable for lists where the number of elements and key values are mostly the same.
8+
9+
"""
10+
11+
12+
def pigeonhole_sort(arr):
13+
Max = max(arr)
14+
Min = min(arr)
15+
size = Max - Min + 1
16+
17+
holes = [0]*size
18+
19+
for i in arr:
20+
holes[i-Min] += 1
21+
22+
i = 0
23+
for count in range(size):
24+
while holes[count] > 0:
25+
holes[count] -= 1
26+
arr[i] = count + Min
27+
i += 1
28+
return arr

‎tests/test_sort.py‎

Lines changed: 5 additions & 0 deletions

0 commit comments

Comments
 (0)