# The Pigeonhole Sort is a sorting algorithm that
# works only for an array of integers.
# It works best when the number of elements and
# the number of possible key values is the same
# which basically means every element is unique
def PigeonHoleSort(array):
# Get the smallest element in the array
smallestIntegerInArray = min(array)
# Get the largest element in the array
largestIntegerInArray = max(array)
# Get an estimate of the number of holes needed
numberOfHoles = largestIntegerInArray - smallestIntegerInArray + 1
# Generate the holes
holes = []
for x in range(0, numberOfHoles):
holes.append(0)
# Fill the holes
# The elements k
for x in array:
holes[x - smallestIntegerInArray] += 1
# pick out the elements from the holes
# one by one and generate the sorted array
sortedArray = []
# your range is the number of holes there are
for count in range(numberOfHoles):
# also, the number of elements inside those holes
while holes[count] > 0:
holes[count] -= 1
# the actual element is count + smallestIntegerInArray
# because we subtracted it earlier
sortedArray.append(count + smallestIntegerInArray)
return sortedArray
array = [8, 8, 10, 6, 5, 2, 4, 7, 3, 1]
print(PigeonHoleSort(array))