How to implement the pigeonhole sorting algorithm in Python
Pigeonhole sort is a non-comparison sorting algorithm that performs sorting in linear time. This algorithm is utilized to sort the integer values where the array length and the range of elements are close. It creates a pigeonhole for each possible data value and places the data items in their corresponding pigeonhole. Lastly, it collects the data items in ascending order to sort the data.
A practical example of pigeonhole sort could be the cabinets in the post offices where every slot represents ZIP codes or other distinguished keys from where the postman can collect the packages. Whenever a new package arrives, it is placed in its proper slot manually.
How it works
The algorithm works in the following steps:
- Find the minimum and maximum values in the array. Also, calculate the range of the data as .
- Create an array of the size of the range and name it pigeonhole.
- Iterate through each array element and place it in the corresponding pigeonhole.
- Iterate through each pigeonhole element and place all the elements back into the array.
Play the following slides to visualize the working of the pigeonhole sort:
Pseudocode
Let’s see the pseudocode of this algorithm before implementing it in any programming language.
min_value := find_min(array)max_value := find_max(array)range := max_value - min_value + 1pigenholes := array[range]for i from 0 to n:push array[i] into pigenholes[array[i] - min]arr_index = 0for i from 0 to range:while(pigenhole[i] is not empty):place pigeonhole elements in array[arr_index]arr_index := arr_index + 1
Code example
Let’s implement the code of pigeonhole sort using Python in the following playground:
def pigeonhole_sort(array):min_value = min(array)max_value = max(array)range_value = max_value - min_value + 1pigeonholes = [[] for _ in range(range_value)]for i in range(len(array)):pigeonholes[array[i] - min_value].append(array[i])arr_index = 0for i in range(range_value):while pigeonholes[i]:array[arr_index] = pigeonholes[i].pop(0)arr_index += 1returnarray = [18, 13, 15, 11, 19, 12, 14, 13]print("Unsorted array:", array)pigeonhole_sort(array)print("Sorted array:", array)
Code explanation
Let’s discuss the code below:
- Lines 2–4: We create variables to store the minimum, maximum, and range of elements.
- Line 6: We define a list of lists to store array elements at their corresponding pigeonholes.
- Lines 8–9: We iterate through each array element and place it in their pigeonholes.
- Lines 11–15: We create a variable
arr_indexto store the index and loop through pigeonhole elements. We use awhileloop to push the values of each pigeonhole to the original array in order. Lastly, we increment thearr_indexafter the transfer of each element. - Lines 18–19: We create an unsorted array and print the array before sorting.
- Lines 21–22: We call the
pigeonhole_sort()function and print the array after sorting.
Complexity
The time and space complexity of the pigeonhole sort algorithm is , where is the length of the array, and is the range of the array elements.
Benefits and limitations
Let’s discuss some benefits and limitations of the Pigeonhole sort.
Benefits
-
Pigeonhole sort is a non-comparison-based algorithm, which means it doesn’t compare elements for sorting. This is beneficial where comparisons are costly.
-
It is a stable algorithm, which means it maintains the order of equal elements.
-
It is a linear time algorithm that performs sorting quickly. It is faster than comparison-based sorting algorithms, i.e., merge sort or quick sort.
Limitations
- Pigeonhole sort requires extra memory space to sort. This could be alarming when the large array size, high data range, or the memory is costly.
- It only works with integer or indexable values. It isn’t easily extendable to other data types.
