Algorithm Speed (2.00) :

Array Size (100) :

Pigeonhole Sort :

Author(s) : Unknown Date : Ancient

Pigeonhole sort is a sorting algorithm that relies on a fixed-size array (pigeonhole) to represent the range of possible values in the input data. It works under the assumption that the data has a limited range of values. Each element in the input array is used as an index to place it in the corresponding pigeonhole. After all elements are placed, the pigeonhole array is iterated through, and the elements within each pigeonhole are output, effectively sorting them. While pigeonhole sort has a time complexity of O(n + 2ᴷ), where k is the range of possible values, it's limited by the requirement of a fixed-size pigeonhole array and a known value range. Its applicability is restricted to specific data scenarios.

Time Complexity	O(n + 2ᴷ)
Best Case	O(n + 2ᴷ)
Worst Case	O(n + 2ᴷ)
Space Complexity	O(2ᴷ)
Stable	Yes

def pigeonhole_sort(arr):
	min_value = min(arr)
	max_value = max(arr)
	size = max_value - min_value + 1
	holes = [[] for i in range(size)]
	for i in arr:
		holes[i - min_value].append(i)
	arr = []
	for i in range(size):
		for item in holes[i]:
			arr.append(item)
	return arr

# Test array
arr = [8, 3, 2, 7, 4, 6, 9]
print('Sorted array is:', pigeonhole_sort(arr))

function pigeonholeSort(arr) {
	let min_value = Math.min(...arr);
	let max_value = Math.max(...arr);
	let size = max_value - min_value + 1;
	let holes = Array(size).fill([]);
	for (let i of arr) {
		holes[i - min_value].push(i);
	}
	let arr = [];
	for (let i = 0; i < size; i++) {
		for (let item of holes[i]) {
			arr.push(item);
		}
	}
	return arr;
	}

// Test array
let arr = [8, 3, 2, 7, 4, 6, 9];
console.log('Sorted array is:', pigeonholeSort(arr));

public static int[] pigeonholeSort(int[] arr) {
	int min_value = Integer.MIN_VALUE;
	int max_value = Integer.MAX_VALUE;
	for (int i : arr) {
		min_value = Math.min(min_value, i);
		max_value = Math.max(max_value, i);
	}
	int size = max_value - min_value + 1;
	int[][] holes = new int[size][];
	for (int i = 0; i < size; i++) {
		holes[i] = new int[0];
	}
	for (int i : arr) {
		holes[i - min_value] = Arrays.copyOf(holes[i - min_value], holes[i - min_value].length + 1);
		holes[i - min_value][holes[i - min_value].length - 1] = i;
	}
	int[] arr_sorted = new int[arr.length];
	int index = 0;
	for (int i = 0; i < size; i++) {
		for (int item : holes[i]) {
			arr_sorted[index++] = item;
		}
	}
	return arr_sorted;
	}

// Test array
int[] arr = {8, 3, 2, 7, 4, 6, 9};
System.out.println('Sorted array is: ' + Arrays.toString(pigeonholeSort(arr)));

func pigeonholeSort(arr []int) []int {
	min_value := arr[0]
	max_value := arr[0]
	for _, val := range arr {
		min_value = min(min_value, val)
		max_value = max(max_value, val)
	}
	size := max_value - min_value + 1
	holes := make([][]int, size)
	for i := range holes {
		holes[i] = []int{}
	}
	for _, val := range arr {
		holes[val - min_value] = append(holes[val - min_value], val)
	}
	arr_sorted := make([]int, 0, len(arr))
	for _, hole := range holes {
		for _, item := range hole {
			arr_sorted = append(arr_sorted, item)
		}
	}
	return arr_sorted
	}

// Test array
arr := []int{8, 3, 2, 7, 4, 6, 9}
fmt.Println('Sorted array is:', pigeonholeSort(arr))

void pigeonhole_sort(int arr[], int n) {
	int min_value = arr[0];
	int max_value = arr[0];
	for (int i = 1; i < n; i++) {
		min_value = min(min_value, arr[i]);
		max_value = max(max_value, arr[i]);
	}
	int size = max_value - min_value + 1;
	int *holes = (int *)malloc(size * sizeof(int));
	for (int i = 0; i < size; i++) {
		holes[i] = 0;
	}
	for (int i = 0; i < n; i++) {
		holes[arr[i] - min_value]++;
	}
	int index = 0;
	for (int i = 0; i < size; i++) {
		for (int j = 0; j < holes[i]; j++) {
			arr[index++] = i + min_value;
		}
	}
	free(holes);
}

// Test array
int arr[] = {8, 3, 2, 7, 4, 6, 9};
int n = sizeof(arr) / sizeof(arr[0]);
pigeonhole_sort(arr, n);
printf('Sorted array is: ');
for (int i = 0; i < n; i++) {
	printf('%d ', arr[i]);
}