-
Notifications
You must be signed in to change notification settings - Fork 0
Pigeonhole Sort
range_of_elements is the difference between the values of the largest and smallest elements.
Pigeonhole Sort is a sorting algorithm based on the Pigeonhole principle. It is marginally slower than Counting Sort, but it also works with negatives, while Counting Sort doesn't. It is probably the best sorting algorithm for integers. It has to do an extra passthrough at the beginning to find the range, something that Counting Sort does not have to do. However, it uses slightly less memory if the smallest element's value is greater than zero.
It works by finding the largest and smallest values in the array and storing that as the range. Then it creates an array of the size of the range, an array of "pigeonholes". It increments appropriate elements in the Pigeonhole array, offset by the minimum. So the smallest value in the original array causes incrementation of the first index in the pigeonhole array. It works by taking the value of every individual element and subtracting the minimum value from it.
Using the following array, the mechanism can be shown:
4, 2, 7, 4, 3
The range of the data is 7 - 2, which is 5. However, we need to add 1 to be inclusive.
Pigeonhole Sort then iterates through the array and placed stuff into the pigeonhole array. It starts with the first element, a 4. We subtract the min (which is 2) from this value, which results in 2. So we increment 2, which is the third element in the Pigeonhole array.
Original array: 4, 2, 7, 4, 3
Pigeonhole array: 0, 0, 1, 0, 0, 0
It does the next element, which is 2. 2 - 2 = 0, so increment the first element (index 0) in the Pigeonhole array.
Original array: 4, 2, 7, 4, 3
Pigeonhole array: 1, 0, 1, 0, 0, 0
It does the next element, a 7. 7 - 2 = 5. So increment index 5.
Original array: 4, 2, 7, 4, 3
Pigeonhole array: 1, 0, 1, 0, 0, 1
The next element is 4. 4 - 2 = 2. Increment the third item, which is index 2.
Original array: 4, 2, 7, 4, 3
Pigeonhole array: 1, 0, 2, 0, 0, 1
Finally it does the last item, which is 3. 3 - 2 = 1. So increment index 1.
Original array: 4, 2, 7, 4, 3
Pigeonhole array: 1, 1, 2, 0, 0, 1
Now we place items into a new array based on the index + minimum value.
Note: In the actual implementation the original array is directly overwritten, but I used a new blank array in this example to visualize changes to it easier.
The first element in Pigeonhole array is 1. We add a 2 (the minimum of the range) to the index (which is a 0) and place it into the new array. We then decrement that index in the Pigeonhole array from 1 to 0. Since it is 0, we move on afterwards.
New array: 2, -, -, -, -
Pigeonhole array: 0, 1, 2, 0, 0, 1
Next we look at index 1 in the Pigeonhole array, which is 1. We add the minimum of the range to the value of the index, which results in a 3. We also decrement index 1 in the Pigeonhole array.
New array: 2, 3, -, -, -
Pigeonhole array: 0, 0, 2, 0, 0, 1
Next is index 2, which has a 2. 2 + 2 = 4. Then we decrement that item in the Pigeonhole array.
New array: 2, 3, 4, -, -
Pigeonhole array: 0, 0, 1, 0, 0, 1
Since there is still 1 in that index in the Pigeonhole array, we need to place another one and decrement again.
New array: 2, 3, 4, 4, -
Pigeonhole array: 0, 0, 0, 0, 0, 1
The next two elements in the Pigeonhole array is blank, so we skip it. We find the last element in the Pigeonhole array is a non-zero, a 1, so we add its index + minimum to the new array. This is 5 + 2 = 7.
New array: 2, 3, 4, 4, 7
Pigeonhole array: 0, 0, 0, 0, 0, 7
The array is now sorted.