Javascript sorting algorithm for counting sort instances

  • 2020-03-30 02:34:17
  • OfStack

Counting sort is a stable sorting algorithm. Count sort USES an additional array Count_arr, where the ith element is the number of elements whose median value in the array Arr to be sorted is equal to I. The elements in Arr are then sorted into the correct positions based on the array Count_arr.
There are four steps:
1. Find the largest and smallest elements in the array to be sorted
2. Count the number of occurrences of each element of value I in the array, and store the ith term of the array Count_arr
3. Add up all counts (start with the first element in Count_arr and add each term to the previous one)
4. Reverse traversal of the original array: place each element I in the Count_arr(I) entry of the new array, subtracting Count_arr(I) from 1 for each element

Example:




function countSort(arr, min, max) {
    var i, z = 0, count = [];

    for (i = min; i <= max; i++) {
        count[i] = 0;
    }

    for (i=0; i < arr.length; i++) {
        count[arr[i]]++;
    }

    for (i = min; i <= max; i++) {
        while (count[i]-- > 0) {
            arr[z++] = i;
        }
    }
    return arr;
}

// test

var i, arr = [];

for (i = 0; i < 100; i++) {
    arr.push(Math.floor(Math.random() * (141)));
}

countSort(arr, 0, 140);


Related articles: