1.8 Counting Sort
Category Algorithm
The essence of counting sort is to transform the input data values into keys stored in an additional array space. As a sorting algorithm with linear time complexity, counting sort requires that the input data must be integers with a definite range.
When the input elements are n integers between 0 and k, its running time is Θ(n + k). Counting sort is not a comparison sort, and it is faster than any comparison sort algorithm.
Since the length of the array C used for counting depends on the range of data in the array to be sorted (equal to the difference between the maximum and minimum values of the array to be sorted plus 1), this makes counting sort require a lot of time and memory for arrays with a large data range. For example: counting sort is the best algorithm for sorting numbers between 0 and 100, but it is not suitable for sorting names in alphabetical order. However, counting sort can be used in the algorithm of radix sort to sort arrays with a large data range.
Understandably, for example, if there are 10 people with different ages, and it is counted that 8 people are younger than person A, then A's age is the 9th, and this method can be used to determine the position of everyone else, thus sorting them. Of course, when there are duplicate ages, special handling is required (to ensure stability), which is why the target array needs to be filled in reverse at the end, and the count of each number needs to be reduced by 1.
The steps of the algorithm are as follows:
(1) Find the maximum and minimum elements in the array to be sorted
(2) Count the number of occurrences of each value i in the array and store it in the ith item of array C
(3) Accumulate all counts (starting from the first element of C, adding each item to the previous one)
(4) Fill the target array in reverse: place each element i in the C(i)th position of the new array, and reduce C(i) by 1 after placing each element
2. Animation Demonstration
Code Implementation
JavaScript
Example
function countingSort(arr, maxValue) {
var bucket = new Array(maxValue+1),
sortedIndex = 0;
arrLen = arr.length,
bucketLen = maxValue + 1;
for (var i = 0; i < arrLen; i++) {
if (!bucket[arr[i]]) {
bucket[arr[i]] = 0;
}
bucket[arr[i]]++;
}
for (var j = 0; j < bucketLen; j++) {
while(bucket[j] > 0) {
arr[sortedIndex++] = j;
bucket[j]--;
}
}
return arr;
}
Python
Example
def countingSort(arr, maxValue):
bucketLen = maxValue+1
bucket = [0]*bucketLen
sortedIndex =0
arrLen = len(arr)
for i in range(arrLen):
if not bucket[arr[i]]:
bucket[arr[i]]=0
bucket[arr[i]]+=1
for j in range(bucketLen):
while bucket[j]>0:
arr[sortedIndex] = j
sortedIndex+=1
bucket[j]-=1
return arr
Go
Example
func countingSort(arr []int, maxValue int) []int {
bucketLen := maxValue + 1
bucket := make([]int, bucketLen) // Array initialized to 0
sortedIndex := 0
length := len(arr)
for i := 0; i < length; i++ {
bucket[arr[i]] += 1
}
for j := 0; j < bucketLen; j++ {
for bucket[j] > 0 {
arr[sortedIndex] = j
sortedIndex += 1
bucket[j] -= 1
}
}
return arr
}
Java
Example
``` public class CountingSort implements IArraySort {
@Override
public int[] sort(int[] sourceArray) throws Exception {
// Make a copy of arr, do not change the content of the parameter
int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
int maxValue = getMaxValue(arr);
return countingSort(arr, maxValue);
}
private int[] countingSort(int[] arr, int maxValue) {
int bucketLen = maxValue + 1;
int[] bucket = new int[bucketLen];
for (int value :
Click here to share notes
-
-
-
-1.0 Top Ten Classic Sorting Algorithms
- 1.8 Counting Sort