Skip to main content

Pigeonhole Sort

Pigeonhole Sort is a sorting algorithm that is used to sort a set of elements that have a small range of values. It is a simple and intuitive algorithm that is similar to counting sort in its approach.

The algorithm works by first determining the range of values that the input elements can take. Then, it creates an array of "pigeonholes" or "buckets" that correspond to each value in the range. Each element is then placed in its corresponding pigeonhole based on its value. Once all the elements have been placed in the pigeonholes, the algorithm iterates over the pigeonholes in order and puts the elements back into the original array in sorted order.

The time complexity of Pigeonhole Sort is O(n+k), where n is the number of elements to be sorted and k is the range of values. However, the algorithm requires additional space to create the array of pigeonholes, which can make it less efficient than other sorting algorithms for large input sizes or when the range of values is very large.

Pigeonhole Sort is a stable sorting algorithm, which means that it preserves the relative order of equal elements in the input. It is also an in-place sorting algorithm, which means that it does not require any additional memory beyond the input array.

Here given code implementation process.

//C program for
//Sort array by using pigeonhole sort
#include <stdio.h>

//Find the minimum element of given array
int find_min(int arr[], int size)
{
	int result = arr[0];
	for (int i = 1; i < size; ++i)
	{
		if (arr[i] < result)
		{
			result = arr[i];
		}
	}
	return result;
}
//Find the maximum element of given array
int find_max(int arr[], int size)
{
	int result = arr[0];
	for (int i = 1; i < size; ++i)
	{
		if (arr[i] > result)
		{
			result = arr[i];
		}
	}
	return result;
}
// Perform the pigeonhole sort of given array
void pigeonhole_sort(int arr[], int size)
{
	if (size < 1)
	{
		return;
	}
	int min = find_min(arr, size);
	int max = find_max(arr, size);
	int hole_range = max - min + 1;
	int hole[hole_range];
	//Loop controlling variables
	int i = 0;
	int j = 0;
	//Set the initial hole value
	for (i = 0; i < hole_range; ++i)
	{
		hole[i] = 0;
	}
	//Count the occurrences of array elements
	for (i = 0; i < size; i++)
	{
		hole[arr[i] - min]++;
	}
	for (i = 0; i < hole_range; i++)
	{
		//Check that whether hole occurrence greater than zero
		while (hole[i] > 0)
		{
			//When occurrence are more than zero
			//Put element value to array
			arr[j] = i + min;
			// Modify the index of array element
			// next element location
			j++;
			//reduce the existing occurrence
			hole[i]--;
		}
	}
}
//print the array elements
void display(int arr[], int size)
{
	int i = 0;
	for (i = 0; i < size; i++)
	{
		printf("  %d", arr[i]);
	}
}
int main()
{
	//Define the collection of integer elements
	int arr[] = {
		7,
		2,
		90,
		4,
		1,
		3,
		46,
		-4,
		-4,
		12,
		6,
		3,
		2
	};
	int size = sizeof(arr) / sizeof(arr[0]);
	printf("After Sort : ");
	display(arr, size);
	pigeonhole_sort(arr, size);
	printf("\nBefore Sort  : ");
	display(arr, size);
	return 0;
}

Output

After Sort :   7  2  90  4  1  3  46  -4  -4  12  6  3  2
Before Sort  :   -4  -4  1  2  2  3  3  4  6  7  12  46  90
// Java program 
// Sort array by using pigeonhole sort
class MySort
{
	//Find the minimum element of given array
	public int find_min(int[] arr, int size)
	{
		int result = arr[0];
		for (int i = 1; i < size; ++i)
		{
			if (arr[i] < result)
			{
				result = arr[i];
			}
		}
		return result;
	}
	//Find the maximum element of given array
	public int find_max(int[] arr, int size)
	{
		int result = arr[0];
		for (int i = 1; i < size; ++i)
		{
			if (arr[i] > result)
			{
				result = arr[i];
			}
		}
		return result;
	}
	// Perform the pigeonhole sort of given array
	public void pigeonhole_sort(int[] arr, int size)
	{
		if (size < 1)
		{
			return;
		}
		int min = find_min(arr, size);
		int max = find_max(arr, size);
		int hole_range = max - min + 1;
		int[] hole = new int[hole_range];
		//Loop controlling variables
		int i = 0;
		int j = 0;
		//Set the initial hole value
		for (i = 0; i < hole_range; ++i)
		{
			hole[i] = 0;
		}
		//Count the occurrences of array elements
		for (i = 0; i < size; i++)
		{
			hole[arr[i] - min]++;
		}
		for (i = 0; i < hole_range; i++)
		{
			//Check that whether hole occurrence greater than zero
			while (hole[i] > 0)
			{
				//When occurrence are more than zero
				//Put element value to array
				arr[j] = i + min;
				// Modify the index of array element
				// next element location
				j++;
				//reduce the existing occurrence
				hole[i]--;
			}
		}
	}
	//print the array elements
	public void display(int[] arr, int size)
	{
		int i = 0;
		for (i = 0; i < size; i++)
		{
			System.out.print("  " + arr[i]);
		}
	}
	public static void main(String[] args)
	{
		MySort obj = new MySort();
		//Define the collection of integer elements
		int[] arr = {
			7,
			2,
			90,
			4,
			1,
			3,
			46,
			-4,
			-4,
			12,
			6,
			3,
			2
		};
		int size = arr.length;
		System.out.print("After Sort : ");
		obj.display(arr, size);
		obj.pigeonhole_sort(arr, size);
		System.out.print("\nBefore Sort  : ");
		obj.display(arr, size);
	}
}

Output

After Sort :   7  2  90  4  1  3  46  -4  -4  12  6  3  2
Before Sort  :   -4  -4  1  2  2  3  3  4  6  7  12  46  90
//Include header file
#include <iostream>

using namespace std;
// C++ program 
// Sort array by using pigeonhole sort
class MySort
{
	public:
		//Find the minimum element of given array
		int find_min(int arr[], int size)
		{
			int result = arr[0];
			for (int i = 1; i < size; ++i)
			{
				if (arr[i] < result)
				{
					result = arr[i];
				}
			}
			return result;
		}
	//Find the maximum element of given array
	int find_max(int arr[], int size)
	{
		int result = arr[0];
		for (int i = 1; i < size; ++i)
		{
			if (arr[i] > result)
			{
				result = arr[i];
			}
		}
		return result;
	}
	// Perform the pigeonhole sort of given array
	void pigeonhole_sort(int arr[], int size)
	{
		if (size < 1)
		{
			return;
		}
		int min = this->find_min(arr, size);
		int max = this->find_max(arr, size);
		int hole_range = max - min + 1;
		int hole[hole_range];
		//Loop controlling variables
		int i = 0;
		int j = 0;
		//Set the initial hole value
		for (i = 0; i < hole_range; ++i)
		{
			hole[i] = 0;
		}
		//Count the occurrences of array elements
		for (i = 0; i < size; i++)
		{
			hole[arr[i] - min]++;
		}
		for (i = 0; i < hole_range; i++)
		{
			//Check that whether hole occurrence greater than zero
			while (hole[i] > 0)
			{
				//When occurrence are more than zero
				//Put element value to array
				arr[j] = i + min;
				// Modify the index of array element
				// next element location
				j++;
				//reduce the existing occurrence
				hole[i]--;
			}
		}
	}
	//print the array elements
	void display(int arr[], int size)
	{
		int i = 0;
		for (i = 0; i < size; i++)
		{
			cout << "  " << arr[i];
		}
	}
};
int main()
{
	MySort obj = MySort();
	int arr[] = {
		7 , 2 , 90 , 4 , 1 , 3 , 46 , -4 , -4 , 12 , 6 , 3 , 2
	};
	int size = sizeof(arr) / sizeof(arr[0]);
	cout << "After Sort : ";
	obj.display(arr, size);
	obj.pigeonhole_sort(arr, size);
	cout << "\nBefore Sort  : ";
	obj.display(arr, size);
	return 0;
}

Output

After Sort :   7  2  90  4  1  3  46  -4  -4  12  6  3  2
Before Sort  :   -4  -4  1  2  2  3  3  4  6  7  12  46  90
//Include namespace system
using System;
// C# program 
// Sort array by using pigeonhole sort
class MySort
{
	//Find the minimum element of given array
	public int find_min(int[] arr, int size)
	{
		int result = arr[0];
		for (int i = 1; i < size; ++i)
		{
			if (arr[i] < result)
			{
				result = arr[i];
			}
		}
		return result;
	}
	//Find the maximum element of given array
	public int find_max(int[] arr, int size)
	{
		int result = arr[0];
		for (int i = 1; i < size; ++i)
		{
			if (arr[i] > result)
			{
				result = arr[i];
			}
		}
		return result;
	}
	// Perform the pigeonhole sort of given array
	public void pigeonhole_sort(int[] arr, int size)
	{
		if (size < 1)
		{
			return;
		}
		int min = find_min(arr, size);
		int max = find_max(arr, size);
		int hole_range = max - min + 1;
		int[] hole = new int[hole_range];
		//Loop controlling variables
		int i = 0;
		int j = 0;
		//Set the initial hole value
		for (i = 0; i < hole_range; ++i)
		{
			hole[i] = 0;
		}
		//Count the occurrences of array elements
		for (i = 0; i < size; i++)
		{
			hole[arr[i] - min]++;
		}
		for (i = 0; i < hole_range; i++)
		{
			//Check that whether hole occurrence greater than zero
			while (hole[i] > 0)
			{
				//When occurrence are more than zero
				//Put element value to array
				arr[j] = i + min;
				// Modify the index of array element
				// next element location
				j++;
				//reduce the existing occurrence
				hole[i]--;
			}
		}
	}
	//print the array elements
	public void display(int[] arr, int size)
	{
		int i = 0;
		for (i = 0; i < size; i++)
		{
			Console.Write("  " + arr[i]);
		}
	}
	public static void Main(String[] args)
	{
		MySort obj = new MySort();
		int[] arr = {
			7 , 2 , 90 , 4 , 1 , 3 , 46 , -4 , -4 , 12 , 6 , 3 , 2
		};
		int size = arr.Length;
		Console.Write("After Sort : ");
		obj.display(arr, size);
		obj.pigeonhole_sort(arr, size);
		Console.Write("\nBefore Sort  : ");
		obj.display(arr, size);
	}
}

Output

After Sort :   7  2  90  4  1  3  46  -4  -4  12  6  3  2
Before Sort  :   -4  -4  1  2  2  3  3  4  6  7  12  46  90
<?php
// Php program 
// Sort array by using pigeonhole sort
class MySort
{
	//Find the minimum element of given array
	public	function find_min( $arr, $size)
	{
		$result = $arr[0];
		for ($i = 1; $i < $size; ++$i)
		{
			if ($arr[$i] < $result)
			{
				$result = $arr[$i];
			}
		}
		return $result;
	}
	//Find the maximum element of given array
	public	function find_max( $arr, $size)
	{
		$result = $arr[0];
		for ($i = 1; $i < $size; ++$i)
		{
			if ($arr[$i] > $result)
			{
				$result = $arr[$i];
			}
		}
		return $result;
	}
	// Perform the pigeonhole sort of given array
	public	function pigeonhole_sort( & $arr, $size)
	{
		if ($size < 1)
		{
			return;
		}
		$min = $this->find_min($arr, $size);
		$max = $this->find_max($arr, $size);
		$hole_range = $max - $min + 1;
      	//Set the initial hole value
		$hole = array_fill(0, $hole_range, 0);
		//Loop controlling variables
		$i = 0;
		$j = 0;
		//Count the occurrences of array elements
		for ($i = 0; $i < $size; $i++)
		{
			$hole[$arr[$i] - $min]++;
		}
		for ($i = 0; $i < $hole_range; $i++)
		{
			//Check that whether hole occurrence greater than zero
			while ($hole[$i] > 0)
			{
				//When occurrence are more than zero
				//Put element value to array
				$arr[$j] = $i + $min;
				// Modify the index of array element
				// next element location
				$j++;
				//reduce the existing occurrence
				$hole[$i]--;
			}
		}
	}
	//print the array elements
	public	function display( & $arr, $size)
	{
		$i = 0;
		for ($i = 0; $i < $size; $i++)
		{
			echo "  ". $arr[$i];
		}
	}
}

function main()
{
	$obj = new MySort();
	//Define the collection of integer elements
	$arr = array(7, 2, 90, 4, 1, 3, 46, -4, -4, 12, 6, 3, 2);
	$size = count($arr);
	echo "After Sort : ";
	$obj->display($arr, $size);
	$obj->pigeonhole_sort($arr, $size);
	echo "\nBefore Sort  : ";
	$obj->display($arr, $size);
}
main();

Output

After Sort :   7  2  90  4  1  3  46  -4  -4  12  6  3  2
Before Sort  :   -4  -4  1  2  2  3  3  4  6  7  12  46  90
// Node Js program 
// Sort array by using pigeonhole sort
class MySort
{
	//Find the minimum element of given array
	find_min(arr, size)
	{
		var result = arr[0];
		for (var i = 1; i < size; ++i)
		{
			if (arr[i] < result)
			{
				result = arr[i];
			}
		}
		return result;
	}
	//Find the maximum element of given array
	find_max(arr, size)
	{
		var result = arr[0];
		for (var i = 1; i < size; ++i)
		{
			if (arr[i] > result)
			{
				result = arr[i];
			}
		}
		return result;
	}
	// Perform the pigeonhole sort of given array
	pigeonhole_sort(arr, size)
	{
		if (size < 1)
		{
			return;
		}
		var min = this.find_min(arr, size);
		var max = this.find_max(arr, size);
		var hole_range = max - min + 1;
     	//Set the initial hole value
		var hole = Array(hole_range).fill(0);
		//Loop controlling variables
		var i = 0;
		var j = 0;
		
		//Count the occurrences of array elements
		for (i = 0; i < size; i++)
		{
			hole[arr[i] - min]++;
		}
		for (i = 0; i < hole_range; i++)
		{
			//Check that whether hole occurrence greater than zero
			while (hole[i] > 0)
			{
				//When occurrence are more than zero
				//Put element value to array
				arr[j] = i + min;
				// Modify the index of array element
				// next element location
				j++;
				//reduce the existing occurrence
				hole[i]--;
			}
		}
	}
	//print the array elements
	display(arr, size)
	{
		var i = 0;
		for (i = 0; i < size; i++)
		{
			process.stdout.write("  " + arr[i]);
		}
	}
}

function main()
{
	var obj = new MySort();
	//Define the collection of integer elements
	var arr = [7, 2, 90, 4, 1, 3, 46, -4, -4, 12, 6, 3, 2];
	var size = arr.length;
	process.stdout.write("After Sort : ");
	obj.display(arr, size);
	obj.pigeonhole_sort(arr, size);
	process.stdout.write("\nBefore Sort  : ");
	obj.display(arr, size);
}
main();

Output

After Sort :   7  2  90  4  1  3  46  -4  -4  12  6  3  2
Before Sort  :   -4  -4  1  2  2  3  3  4  6  7  12  46  90
#  Python 3 program 
#  Sort array by using pigeonhole sort
class MySort :
	# Find the minimum element of given array
	def find_min(self, arr, size) :
		result = arr[0]
		i = 1
		while (i < size) :
			if (arr[i] < result) :
				result = arr[i]
			
			i += 1
		
		return result
	
	# Find the maximum element of given array
	def find_max(self, arr, size) :
		result = arr[0]
		i = 1
		while (i < size) :
			if (arr[i] > result) :
				result = arr[i]
			
			i += 1
		
		return result
	
	#  Perform the pigeonhole sort of given array
	def pigeonhole_sort(self, arr, size) :
		if (size < 1) :
			return
		
		min = self.find_min(arr, size)
		max = self.find_max(arr, size)
		hole_range = max - min + 1
		hole = [0] * hole_range
		# Loop controlling variables
		i = 0
		j = 0

		# Count the occurrences of array elements
		i = 0
		while (i < size) :
			hole[arr[i] - min] += 1
			i += 1
		
		i = 0
		while (i < hole_range) :
			# Check that whether hole occurrence greater than zero
			while (hole[i] > 0) :
				# When occurrence are more than zero
				# Put element value to array
				arr[j] = i + min
				#  Modify the index of array element
				#  next element location
				j += 1
				# reduce the existing occurrence
				hole[i] -= 1
			
			i += 1
		
	
	# print the array elements
	def display(self, arr, size) :
		i = 0
		while (i < size) :
			print("  ", arr[i], end = "")
			i += 1
		
	

def main() :
	obj = MySort()
	# Define the collection of integer elements
	arr = [7, 2, 90, 4, 1, 3, 46, -4, -4, 12, 6, 3, 2]
	size = len(arr)
	print("After Sort : ", end = "")
	obj.display(arr, size)
	obj.pigeonhole_sort(arr, size)
	print("\nBefore Sort  : ", end = "")
	obj.display(arr, size)

if __name__ == "__main__": main()

Output

After Sort :    7   2   90   4   1   3   46   -4   -4   12   6   3   2
Before Sort  :    -4   -4   1   2   2   3   3   4   6   7   12   46   90
#  Ruby program 
#  Sort array by using pigeonhole sort
class MySort

	# Find the minimum element of given array
	def find_min(arr, size)
	
		result = arr[0]
		i = 1
		while (i < size)
		
			if (arr[i] < result)
			
				result = arr[i]
			end
			i += 1
		end
		return result
	end
	# Find the maximum element of given array
	def find_max(arr, size)
	
		result = arr[0]
		i = 1
		while (i < size)
		
			if (arr[i] > result)
			
				result = arr[i]
			end
			i += 1
		end
		return result
	end
	#  Perform the pigeonhole sort of given array
	def pigeonhole_sort(arr, size)
	
		if (size < 1)
		
			return
		end
		min = self.find_min(arr, size)
		max = self.find_max(arr, size)
		hole_range = max - min + 1
		hole = Array.new(hole_range) {0}
		# Loop controlling variables
		i = 0
		j = 0

		# Count the occurrences of array elements
		i = 0
		while (i < size)
		
			hole[arr[i] - min] += 1
			i += 1
		end
		i = 0
		while (i < hole_range)
		
			# Check that whether hole occurrence greater than zero
			while (hole[i] > 0)
			
				# When occurrence are more than zero
				# Put element value to array
				arr[j] = i + min
				#  Modify the index of array element
				#  next element location
				j += 1
				# reduce the existing occurrence
				hole[i] -= 1
			end
			i += 1
		end
	end
	# print the array elements
	def display(arr, size)
	
		i = 0
		while (i < size)
		
			print("  ", arr[i])
			i += 1
		end
	end
end
def main()

	obj = MySort.new()
	# Define the collection of integer elements
	arr = [7, 2, 90, 4, 1, 3, 46, -4, -4, 12, 6, 3, 2]
	size = arr.length
	print("After Sort : ")
	obj.display(arr, size)
	obj.pigeonhole_sort(arr, size)
	print("\nBefore Sort  : ")
	obj.display(arr, size)
end
main()

Output

After Sort :   7  2  90  4  1  3  46  -4  -4  12  6  3  2
Before Sort  :   -4  -4  1  2  2  3  3  4  6  7  12  46  90
// Scala program 
// Sort array by using pigeonhole sort
class MySort
{
	//Find the minimum element of given array
	def find_min(arr: Array[Int], size: Int): Int = {
		var result: Int = arr(0);
		var i: Int = 1;
		while (i < size)
		{
			if (arr(i) < result)
			{
				result = arr(i);
			}
			i += 1;
		}
		return result;
	}
	//Find the maximum element of given array
	def find_max(arr: Array[Int], size: Int): Int = {
		var result: Int = arr(0);
		var i: Int = 1;
		while (i < size)
		{
			if (arr(i) > result)
			{
				result = arr(i);
			}
			i += 1;
		}
		return result;
	}
	// Perform the pigeonhole sort of given array
	def pigeonhole_sort(arr: Array[Int], size: Int): Unit = {
		if (size < 1)
		{
			return;
		}
		var min: Int = find_min(arr, size);
		var max: Int = find_max(arr, size);
		var hole_range: Int = max - min + 1;
		var hole: Array[Int] = Array.fill[Int](hole_range)(0);
		//Loop controlling variables
		var i: Int = 0;
		var j: Int = 0;
		
		//Count the occurrences of array elements
		i = 0;
		while (i < size)
		{
			hole(arr(i) - min) += 1;
			i += 1;
		}
		i = 0;
		while (i < hole_range)
		{
			//Check that whether hole occurrence greater than zero
			while (hole(i) > 0)
			{
				//When occurrence are more than zero
				//Put element value to array
				arr(j) = i + min;
				// Modify the index of array element
				// next element location
				j += 1;
				//reduce the existing occurrence
				hole(i) -= 1;
			}
			i += 1;
		}
	}
	//print the array elements
	def display(arr: Array[Int], size: Int): Unit = {
		var i: Int = 0;
		while (i < size)
		{
			print("  " + arr(i));
			i += 1;
		}
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var obj: MySort = new MySort();
		//Define the collection of integer elements
		var arr: Array[Int] = Array(7, 2, 90, 4, 1, 3, 46, -4, -4, 12, 6, 3, 2);
		var size: Int = arr.length;
		print("After Sort : ");
		obj.display(arr, size);
		obj.pigeonhole_sort(arr, size);
		print("\nBefore Sort  : ");
		obj.display(arr, size);
	}
}

Output

After Sort :   7  2  90  4  1  3  46  -4  -4  12  6  3  2
Before Sort  :   -4  -4  1  2  2  3  3  4  6  7  12  46  90
// Swift program 
// Sort array by using pigeonhole sort
class MySort
{
	//Find the minimum element of given array
	func find_min(_ arr: [Int], _ size: Int) -> Int
	{
		var result: Int = arr[0];
		var i: Int = 1;
		while (i < size)
		{
			if (arr[i] < result)
			{
				result = arr[i];
			}
			i += 1;
		}
		return result;
	}
	//Find the maximum element of given array
	func find_max(_ arr: [Int], _ size: Int) -> Int
	{
		var result: Int = arr[0];
		var i: Int = 1;
		while (i < size)
		{
			if (arr[i] > result)
			{
				result = arr[i];
			}
			i += 1;
		}
		return result;
	}
	// Perform the pigeonhole sort of given array
	func pigeonhole_sort(_ arr: inout[Int], _ size: Int)
	{
		if (size < 1)
		{
			return;
		}
		let min: Int = self.find_min(arr, size);
		let max: Int = self.find_max(arr, size);
		let hole_range: Int = max - min + 1;
		var hole: [Int] = Array(repeating: 0, count: hole_range);
		//Loop controlling variables
		var i: Int = 0;
		var j: Int = 0;
		
		//Count the occurrences of array elements
		i = 0;
		while (i < size)
		{
			hole[arr[i] - min] += 1;
			i += 1;
		}
		i = 0;
		while (i < hole_range)
		{
			//Check that whether hole occurrence greater than zero
			while (hole[i] > 0)
			{
				//When occurrence are more than zero
				//Put element value to array
				arr[j] = i + min;
				// Modify the index of array element
				// next element location
				j += 1;
				//reduce the existing occurrence
				hole[i] -= 1;
			}
			i += 1;
		}
	}
	//print the array elements
	func display(_ arr: [Int], _ size: Int)
	{
		var i: Int = 0;
		while (i < size)
		{
			print("  ", arr[i], terminator: "");
			i += 1;
		}
	}
}
func main()
{
	let obj: MySort = MySort();
	//Define the collection of integer elements
	var arr: [Int] = [7, 2, 90, 4, 1, 3, 46, -4, -4, 12, 6, 3, 2];
	let size: Int = arr.count;
	print("After Sort : ", terminator: "");
	obj.display(arr, size);
	obj.pigeonhole_sort(&arr, size);
	print("\nBefore Sort  : ", terminator: "");
	obj.display(arr, size);
}
main();

Output

After Sort :    7   2   90   4   1   3   46   -4   -4   12   6   3   2
Before Sort  :    -4   -4   1   2   2   3   3   4   6   7   12   46   90

Pigeonhole Sort works in the following way:

  1. Determine the range of values: Find the minimum and maximum values in the input array. The range of values is then defined as the difference between the maximum and minimum values plus one.

  2. Create the pigeonholes: Create an array of pigeonholes that is large enough to hold all the input elements. The size of the array is equal to the range of values.

  3. Place elements in the pigeonholes: Iterate over the input array and place each element in its corresponding pigeonhole based on its value. For example, if an element has value 5 and the minimum value is 2, then it would be placed in the third pigeonhole (since the third pigeonhole corresponds to the value 5 - 2 = 3).

  4. Put elements back in sorted order: Iterate over the pigeonholes in order and put the elements back into the original array in sorted order. For each pigeonhole, iterate over the elements in the pigeonhole and place them back into the original array.

  5. The array is now sorted: The original array now contains the elements sorted in ascending order.

Here's an example to help illustrate the algorithm. Suppose we have the following array of 7 elements:

[5, 2, 8, 1, 4, 5, 6]

  1. Determine the range of values: The minimum value is 1 and the maximum value is 8, so the range of values is 8 - 1 + 1 = 8.

  2. Create the pigeonholes: Create an array of 8 pigeonholes.

  3. Place elements in the pigeonholes: Iterate over the input array and place each element in its corresponding pigeonhole based on its value.

    • 1 goes in pigeonhole 0 (since 1 - 1 = 0)
    • 2 goes in pigeonhole 1 (since 2 - 1 = 1)
    • 4 goes in pigeonhole 3 (since 4 - 1 = 3)
    • 5 goes in pigeonhole 4 (since 5 - 1 = 4)
    • 5 goes in pigeonhole 4 (since 5 - 1 = 4)
    • 6 goes in pigeonhole 5 (since 6 - 1 = 5)
    • 8 goes in pigeonhole 7 (since 8 - 1 = 7)

    The pigeonholes now contain the following elements:

    [1, 1, 0, 1, 2, 1, 0, 1]

  4. Put elements back in sorted order: Iterate over the pigeonholes in order and put the elements back into the original array in sorted order.

    • Pigeonhole 0 contains no elements
    • Pigeonhole 1 contains 1 element, which is placed in the first position of the output array: [1]
    • Pigeonhole 2 contains no elements
    • Pigeonhole 3 contains 1 element, which is placed in the second position of the output array: [1, 2]
    • Pigeonhole 4 contains 2 elements, which are placed in the third and fourth positions of the output array: [1, 2, 5, 5]
    • Pigeonhole 5 contains 1 element, which is placed in the fifth position of the output array: [1, 2, 5, 5, 6]
    • Pigeonhole 6 contains no elements
    • Pigeonhole 7 contains 1 element, which is placed in the sixth position of the output array: [1, 2, 5, 5, 6, 8]
Last updated on by Kalkicode




Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment