Pigeonhole Sort

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


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







© 2021, kalkicode.com, All rights reserved