From: Github at KLh2333
Algorithm principle
Counting sort is a distributed sort. Distributed sorting uses organized secondary data structures, called buckets, to get sorted arrays. It is a good algorithm for sorting integers (it is an integer sorting algorithm), but requires more memory to hold temporary arrays.
The main process is to get a count array from the original array, and then recover the sorted array from the count array: original array — > count array — > sorted array. As for how to get the count array, and how to restore the count array from the original array, look at the following example.
Given a fairly conventional array (the minimum value of the array is 0, each item in the array is an integer, and the values are distributed between 0 and N), the conventional counting sort process looks like this:
- Array subscripts are naturally sorted (from small to large), so we associate the subscripts of the count array with the values of the original array ** (this association rules are in your mind) **. The simplest association is that if the counter array is subscript 0, it corresponds to the array value 0 in the original array. The maximum value of the index in the counter array corresponds to the maximum value in the original array.
- Find the maximum N in the original array and create a count array of length N + 1. For example, if the maximum value of the array is 20, the maximum value of the subscript of the counter array must be 20 (the array subscript range is 0 to 20). Then the length of the array is 20 + 1 = 21.
- After creating the count array, the count array is generated and the number of values in the original array is counted. For example, if a 2 occurs three times and a 1 occurs four times in the original array, we would write a 3 at index 2 and a 4 at index 1 in the counter array.
- Once the count array is generated, we can restore the sorted array. The subscript of the counter array records the occurrence of the value in the original array, and the value of the counter array records the occurrence of the value in the original array. For example, if the counter array is [3, 4, 1], then it restores the sorted array to be [0, 0, 0, 1, 1, 1, 2].
Problems and Optimization
There is a slight problem with the above steps:
- What if I have a negative integer?
- If the maximum value in the array is 650, but the entire array is in the range of 600 to 650, then if you create an array of length 651, isn’t 600 of the array length wasted?
The solution to this little problem is to change the association between the index of the count array and the value in the original array. That is, make adjustments to step 1 above. The specific correlation method is to find the maximum value Max and the minimum value min in the array, and the subscript 0 of the count array no longer corresponds to the value 0 in the original array, but to the minimum value min in the original array. The length of the count array is: max-min + 1; Index + min = value, where index is the index of the count array, min is the minimum value in the original array, and value is the value in the original array corresponding to the index of the current count array.
After modifying Step 1, the following process can be carried out step by step.
Algorithm diagram
Suppose you have an array [1, -2, -3, 1, 0, 0, 0, 2, 2, 2, 2, 4, 1, 1, 3, 3, 3, 5, 5, 4] and sort it from smallest to largest.
As can be seen from the diagram above, count sort is suitable for the case that the array range is not so large. If the array range is extremely large, the required count array will be extremely long, and the consumption of memory space will be not optimistic.
Javascript code
/** * Count sort, no optimized space * input: array to be sorted * output: array sorted from smallest to largest */
function countingSort1(arr) {
/** * find the maximum value in the array, * create the corresponding length of the count array (js is dynamic, this step is not ok) */
let maxValue = findMaxValue(arr);
let counts = new Array(maxValue + 1); // Create count array
// let counts = [];
// Generate count array
for (let i = 0; i < arr.length; i++) {
let index = arr[i]; // The value of the original array is used as the index of the count array
if(! counts[index]) { counts[index] =0; // If no count exists, initialize to 0 first
}
/ / count
counts[index]++;
}
Restore the sorted array from the count array.
let sortedIndex = 0;
for (let i = 0; i < counts.length; i++) {
while (counts[i] > 0) { arr[sortedIndex++] = i; counts[i]--; }}return arr;
}
/** * Count sort, optimized space * input: array to be sorted * output: smallest to largest sorted array */
function countingSort2(arr) {
/** * find the maximum and minimum values in the array. * The maximum and minimum values are used to determine the length of the array and create count arrays (js is dynamic, this step is not ok) */
let maxValue = findMaxValue(arr);
let minValue = findMinValue(arr);
let counts = new Array(maxValue - minValue + 1); // Create count array
// let counts = [];
// Generate count array
for (let i = 0; i < arr.length; i++) {
// Index + minValue = value
let index = arr[i] - minValue;
if(! counts[index]) { counts[index] =0;
}
counts[index]++;
}
// Restore the sorted array from the count array
let sortedIndex = 0;
for (let i = 0; i < counts.length; i++) {
while (counts[i] > 0) {
arr[sortedIndex++] = i + minValue; // Index + minValue = valuecounts[i]--; }}return arr;
}
/** * Find the maximum value in array * input: array * output: maximum value in array */
function findMaxValue(arr) {
let max = arr[0];
for (let i = 1; i < arr.length; i++) {
if(max < arr[i]) { max = arr[i]; }}return max;
}
/** * Find the minimum value in array * input: array * output: maximum value in array */
function findMinValue(arr) {
let min = arr[0];
for (let i = 1; i < arr.length; i++) {
if(min > arr[i]) { min = arr[i]; }}return min;
}
/ / test
let testArr = [9.4.6.7.1.3.2.5];
console.log(countingSort1(testArr));
let testArr2 = [1, -2, -3.1.0.0.0.2.2.2.2.4.1.1.3.3.3.5.5.4];
console.log(countingSort2(testArr2));
Copy the code