Algorithm Speed (2.00) :

Array Size (100) :

Pigeonhole Sort :

Author(s) : Harold H. Seward Date : 1954

Pigeonhole sorting is a sorting algorithm that is suitable for sorting lists of elements where the number of elements and the number of possible key values are approximately the same. It requires O(n + Range) time where n is number of elements in input array and 'Range' is number of possible values in array.

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

def pigeonhole_sort(arr):
	min_val = min(arr)
	max_val = max(arr)
	size = max_val - min_val + 1
	holes = [0] * size
	for x in arr:
		holes[x - min_val] += 1
	i = 0
	for count in range(size):
		while holes[count] > 0:
			holes[count] -= 1
			arr[i] = count + min_val
			i += 1

function pigeonholeSort(arr) {
	let min = Math.min(...arr);
	let max = Math.max(...arr);
	let size = max - min + 1;
	let holes = new Array(size).fill(0);
	for (let i = 0; i < arr.length; i++) {
		holes[arr[i] - min]++;
	}
	let i = 0;
	for (let count = 0; count < size; count++) {
		while (holes[count] > 0) {
			holes[count]--;
			arr[i] = count + min;
			i++;
		}
	}
}

public static void pigeonholeSort(int[] arr) {
	int min = arr[0];
	int max = arr[0];
	for (int i = 1; i < arr.length; i++) {
		if (arr[i] < min) min = arr[i];
		if (arr[i] > max) max = arr[i];
	}
	int size = max - min + 1;
	int[] holes = new int[size];
	for (int i = 0; i < arr.length; i++) {
		holes[arr[i] - min]++;
	}
	int i = 0;
	for (int count = 0; count < size; count++) {
		while (holes[count] > 0) {
			holes[count]--;
			arr[i] = count + min;
			i++;
		}
	}
}

func pigeonholeSort(arr []int) {
	min := arr[0]
	max := arr[0]
	for _, v := range arr {
		if v < min {
			min = v
		}
		if v > max {
			max = v
		}
	}
	size := max - min + 1
	holes := make([]int, size)
	for _, v := range arr {
		holes[v-min]++
	}
	i := 0
	for count := 0; count < size; count++ {
		for holes[count] > 0 {
			holes[count]--
			arr[i] = count + min
			i++
		}
	}
}

void pigeonholeSort(int arr[], int n) {
	int min = arr[0];
	int max = arr[0];
	for (int i = 1; i < n; i++) {
		if (arr[i] < min) min = arr[i];
		if (arr[i] > max) max = arr[i];
	}
	int size = max - min + 1;
	int *holes = (int *)calloc(size, sizeof(int));
	for (int i = 0; i < n; i++) {
		holes[arr[i] - min]++;
	}
	int i = 0;
	for (int count = 0; count < size; count++) {
		while (holes[count] > 0) {
			holes[count]--;
			arr[i] = count + min;
			i++;
		}
	}
	free(holes);
}