Algorithm Speed (2.00) :

Array Size (100) :

Counting Sort :

Author(s) : Unknown Date : 1960s

Counting sort is a sorting algorithm that works well when the input data has a limited range of values. It creates a temporary array (counting array) with a size equal to the range of possible values. Each element in the input array is used as an index to increment the corresponding element in the counting array. The counting array now represents the frequency of each value in the original array. By iterating through the counting array and using the frequencies to place elements in the output array, the sorted output is generated. Counting sort has a time complexity of O(n + r), where r is the range of possible values. However, it requires additional space for the counting array and is most effective when the range of values is relatively small compared to the input size.

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

def counting_sort(arr):
	min_value = min(arr)
	max_value = max(arr)
	size = max_value - min_value + 1
	count = [0] * size
	for i in arr:
		count[i - min_value] += 1
	arr = []
	i = 0
	for j in range(size):
		for _ in range(count[j]):
			arr.append(j + min_value)
			i += 1
	return arr

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

function countingSort(arr) {
	let min_value = Math.min(...arr);
	let max_value = Math.max(...arr);
	let size = max_value - min_value + 1;
	let count = Array(size).fill(0);
	for (let i of arr) {
		count[i - min_value]++;
	}
	let arr_sorted = [];
	let index = 0;
	for (let i = 0; i < size; i++) {
		for (let j = 0; j < count[i]; j++) {
			arr_sorted[index++] = i + min_value;
		}
	}
	return arr_sorted;
	}

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

public static int[] countingSort(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[] count = new int[size];
	for (int i : arr) {
		count[i - min_value]++;
	}
	int[] arr_sorted = new int[arr.length];
	int index = 0;
	for (int i = 0; i < size; i++) {
		for (int j = 0; j < count[i]; j++) {
			arr_sorted[index++] = i + min_value;
		}
	}
	return arr_sorted;
	}

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

func countingSort(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
	count := make([]int, size)
	for _, val := range arr {
		count[val - min_value]++
	}
	arr_sorted := make([]int, 0, len(arr))
	index := 0
	for i := 0; i < size; i++ {
		for j := 0; j < count[i]; j++ {
			arr_sorted = append(arr_sorted, i + min_value)
		}
	}
	return arr_sorted
	}

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

void counting_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 count[size] = {0};
	for (int i = 0; i < n; i++) {
		count[arr[i] - min_value]++;
	}
	int output[n];
	int index = 0;
	for (int i = 0; i < size; i++) {
		for (int j = 0; j < count[i]; j++) {
			output[index++] = i + min_value;
		}
	}
	for (int i = 0; i < n; i++) {
		arr[i] = output[i];
	}
	}

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