By Samar Qureshi; ICS4U

What is pigeonhole sorting?

<aside> 📌 A non-comparison sorting algorithm that takes elements of a given array and temporarily stores them in a separate array of initially empty "pigeonholes". After being systematically ordered in the pigeonhole array, the elements are then transferred back to the original array in increasing order.

</aside>

• Optimal for arrays with elements where the number of elements and the range is approximately the same
• Cannot sort non-integers
• The verb "pigeonhole" means to categorize something in a restrictive way, but used to refer to cubicles for pigeons for delivering letters
• In math, the pigeonhole principle states that if $n$ items are put into $m$ containers, with $n > m$, then at least one container must contain more than one item

Step by step explanation

<aside> 💡 Given the array: 13 2 21 19 6 13 15 2 15 16, let's sort it in increasing order.

</aside>

Step 1: Find the minimum and maximum values in the array

• We will iterate through every value of the array, and compare it to the first value in the array.
• In this case, our minimum value will be 21, and our minimum value will be 2

//max and min values start off as the first element in the array
int min = arr[0];
int max = arr[0];

for(int h=0; h<arr.length; h++) { 
	    	 //finds the maximum and minimum values
	    	  
	if(arr[h] > max) { //finds the maximum value
			max = arr[h];
	}
	         
	else if(arr[h] < min) { //finds the minimum value
			min = arr[h];
	}

}

Step 2: Calculate the range of the elements using 'max-min+1'

int range = max - min + 1; //calculates the range

• Our range is calculated as 21 - 2 + 1 = 20