Learn the counting sort of sorting algorithm

“This is the 10th day of my participation in the August Gwen Challenge.

Time complexity O(n) sorting algorithm

Time complexity O(n)

It’s also called linear sorting

The next three sorting algorithms are sorting algorithms that are not based on comparisons, that do not involve comparisons between elements

The data to be sorted is very demanding and needs to be applicable to scenarios

Counting sort VS bucket sort VS radix sort

• Counting sort: only one key is stored per bucket.
• Bucket sort: Each bucket stores a range of values
• Radix sort: Buckets are allocated based on each digit of the key value

Count sorting

• Counting sort, not comparison-based sorting algorithm;
• The core is to convert the input data values into keys and store them in the extra array space
• It’s an algorithm that swaps space for time
• Count sort can only be used in scenarios where the data range is small. If the data range K is much larger than the sorted data n, count sort is not suitable
• I want to convert it to a non-negative integer

• Time complexity: O(n+ K)
• Space complexity: O(n+ K)

The principle of

1. Look for the largest value in the array;
2. Create a new array based on (maximum value +1) to convert data values to key stores with subscripts [0… maxValue]
3. Storage: Count the number of each element, store, so that the old array of values as the subscript, the number of the same value as the value of the new array
4. The neat thing about this is that buckets are sorted by their subscripts
5. Go through it from small to large

// n is the length of the array
function countSort (arr, n) {
    if (arr.length <= 1) return arr;
    // Find the largest value in the array;
    let maxValue = arr[0];
    for (let i = 1; i < n; i++) {
        if(arr[i] >= maxValue) { maxValue = arr[i]; }}// Create a new array for converting data values to key stores
    // the subscript is [0... maxValue]
    let bucket = new Array(maxValue + 1);

    // Count the number of each element and store it
    // This results in a new array with the values of the old array as subscripts and the number of values of the same array as values
    for (let i =0; i < n; i++) {
        if(! bucket[arr[i]]) { bucket[arr[i]] =0;
        }
        bucket[arr[i]]++;
    }
    // PS: the bucket array is sorted by its subscripts
    // So, just go through it from small to large
    // Iterate over the new array
    let index = 0;
    for (let j = 0; j < maxValue + 1; j++) {
        // Assign to arR when bucket has a value
        while (bucket[j] > 0) { arr[index++] = j; bucket[j]--; }}}Copy the code

Bucket sort

Bucket sort is an upgrade of counting sort

• Time complexity: O(n)
• Space complexity: O(n)

The principle of

The data to be sorted is sorted into several ordered buckets, and the data in each bucket is sorted separately.

The sorting in the bucket is finished, and then the data in each bucket is taken out in turn, and the sequence is orderly.

Bucket sort is suitable for external sort. The data is stored on an external disk,

The amount of data is large and the memory is limited. Therefore, the data cannot be loaded into the memory

steps

1. Walk through the array, find the smallest value, and the largest value
2. Identify multiple buckets, each bucket has a range,
3. Go through the array, put the data in each bucket,
4. The data in the bucket is sorted separately
5. Finally, take them out one by one, and you’re done sorting buckets

Radix sort

Radix sort requires that the data to be sorted be divided into independent bits for comparison, and there is a progressive relationship between the bits.

If the high value of data A is larger than that of data B, then the remaining low values are not compared

The data range of each bit should not be too large, and if it can be sorted using a linear sorting algorithm,

Otherwise the time of radix sort would not be O (n)

• Noncomparative sort
• It’s essentially a multi-keyword sort
• A kind of barrel thinking

Algorithm thought

If you have an array [123,321,432,654], sort each element by the units digit.

After sorting, we continue sorting the new array by tens, and finally, we count the hundreds, so that we have the sorted array

//LSD Radix Sort
var counter = [];
function radixSort(arr, maxDigit) {
    var mod = 10;
    var dev = 1;
    for (var i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {
        for(var j = 0; j < arr.length; j++) {
            var bucket = parseInt((arr[j] % mod) / dev);
            if(counter[bucket]==null) {
                counter[bucket] = [];
            }
            counter[bucket].push(arr[j]);
        }
        var pos = 0;
        for(var j = 0; j < counter.length; j++) {
            var value = null;
            if(counter[j]! =null) {
                while((value = counter[j].shift()) ! =null) { arr[pos++] = value; }}}}return arr;
}
Copy the code