This is the 24th day of my participation in Gwen Challenge

Stable version of counting sort

Before you can learn about radix sort, you need to know a stable version of counting sort.

Before the understanding of counting sort, just the plain version of counting sort, in addition, there is a stable version of counting sort.

Simple version of the counting sequence, just for integer sorting, of course, no problem, but in some sort of similar to students’ test scores scenario, this demand guarantee sorted, in the order of originally equal element in an array of constant, that is to say, for example, for two of the same number, comes first in the input array number, It also comes first in the output array.

Grade table, figure from xiao Grey’s article

If it’s the naive version of counting sort, the counting array looks like this.

Plain version count sort to get count array, figure from the small grey article

In the stable version of counting sort, the array starts with the second element, and each element is added to the sum of the previous elements.

The purpose of this is to have the value stored in the count array equal to the final sort position of the corresponding integer.

For example, in the figure below, the value with the subscript 9 is 5, which represents the 5th sorted position of the integer 9.

Stable version count sort to get count array, figure from the small grey article

Then create an output array of the same size as the array of values you want to sort, and iterate through the score table at the beginning to get the ranking of all the transcripts from back to front.

If the score of little green is 95, then the value of subscript 5 in the count array — 4, ranking 4 is the rank of little green. Write the result of little green into the result array, and subtract the value of subscript 5 from the count array by 1(if the next time you encounter the same score, the ranking will be 4-1=3).

Small green grades sort, figure from small gray article

White score is 94, then the value of subscript 4 in the count array — 2, ranking 2 is the rank of white, write the result of white, and subtract the value of subscript 4 in the count array by 1(if the next time you encounter the same score, ranking 2-1=1).

Small white grades sort, figure from small gray article

Subsequent traversal process and so on, finally can get a little red and green clear sort.

The order of little red and little green, figure from the article of little Gray

So that’s the stable version of counting sort.

What is radix sort

Radix sort is sorted by the number’s “bits”, also known as significant bits and radix.

A bit is a bit in a base system, such as base 10 in decimal and base 100 in hundred… So we can sort by tens of millions of equal bits.

Radix sort can sort not only for a given set of mobile phone numbers, but also for English words. In these complex combinations of elements, radix sort breaks the sorting into stages, each of which counts a single character or number in the same number of turns as the element.

For example, there are the following letters.

In each round, the digits, tens, and hundreds of letters (according to the ASCII code value of the letter) are counted and sorted once, which is the radix sort process. This kind of radix sort is also called MSD(sort from highest priority), as well as LSD(sort from lowest priority).

If you encounter a word with a different number of characters, for example

// apple
// his
// movie
// age
// hi
// company
Copy the code

The longest word here, company, is 7 characters long, and zeros are added to the ends of other words that are less than 7 characters long.

When sorting, use 0 as the smallest number.

// apple00
// his0000
// movie00
// age0000
// hi00000
// company
Copy the code

Code implementation

/** * find the maximum value of the array *@param {array} Array Array to search for *@param {function} CompareFn // Compare with defaultCompare * by default@returns {number} Returns the maximum found in the array */
export function findMaxValue(array, compareFn = defaultCompare) {
  if (array && array.length > 0) {
    let max = array[0];
    for (let i = 1; i < array.length; i++) {
      if(compareFn(max, array[i]) === Compare.LESS_THAN) { max = array[i]; }}return max;
  }
  return undefined;
}
/** * find the minimum value of the array *@param {array} Array Array to search for *@param {function} CompareFn // Compare with defaultCompare * by default@returns {number} Returns the minimum found in the array */
export function findMinValue(array, compareFn = defaultCompare) {
  if (array && array.length > 0) {
    let min = array[0];
    for (let i = 1; i < array.length; i++) {
      if(compareFn(min, array[i]) === Compare.BIGGER_THAN) { min = array[i]; }}return min;
  }
  return undefined;
}
/** * Calculate bucket index *@param {number} Value Specifies the value of the location *@param {number} MinValue Specifies the minimum value * in the minValue array@param {number} SignificantDigit Indicates the valid bit *@param {number } RadixBase, sort in base 10, default base 10 *@return {number} The value corresponds to the index of the bucket range */
const getBucketIndex = (value, minValue, significantDigit, radixBase) = >
  // Distribute elements into buckets according to different interval spans
  Math.floor(((value - minValue) / significantDigit) % radixBase);

/** * Sort by significant bits (base) *@param {array} Array Array to be sorted *@param {number} RadixBase, sort in base 10, default base 10 *@param {number} SignificantDigit Indicates the valid bit *@param {number} MinValue Specifies the minimum value of the minValue array@returns {array} Returns the sorted array */
const countingSortForRadix = (array, radixBase, significantDigit, minValue) = > {
  let bucketsIndex;
  const buckets = []; // Bucket variables
  const aux = [];
  // Use radixBase to initialize buckets, 0 by default
  for (let i = 0; i < radixBase; i++) { // First, we initialize buckets based on the cardinality. Since we are sorting decimal numbers, we need 10 buckets.
    buckets[i] = 0;
  }
  // Count sort (stable sort of count sort)
  / / count sorting article: https://mp.weixin.qq.com/s/WGqndkwLlzyVOHOdGK7X4Q
  for (let i = 0; i < array.length; i++) { // Then, we will base on the array
    bucketsIndex = getBucketIndex(array[i], minValue, significantDigit, radixBase); // Calculate the bucket index
    buckets[bucketsIndex]++; // Perform counting operations based on the bucket index
  }
  for (let i = 1; i < radixBase; i++) { // Calculate the cumulative result to get the correct count, traversing from 1 to radixBase.
    buckets[i] += buckets[i - 1]; // Starting with the second element, each element is added to the sum of the previous elements.
  }
  // When the count is complete, traverse the array and move the value back to the original array, using aux auxiliary array to store the value
  for (let i = array.length - 1; i >= 0; i--) {   // For each value in the original array
    bucketsIndex = getBucketIndex(array[i], minValue, significantDigit, radixBase); // Computes the bucket index of the current element
    aux[--buckets[bucketsIndex]] = array[i]; // Perform decrement on the element in the current bucket index to get its correct position in the array index
  }
  // After the index is calculated, the current traversal element is stored in the corresponding position in AUX
  for (let i = 0; i < array.length; i++) {
    array[i] = aux[i];
  }
  return array;
};
Radix sort / * * * * refer to the article: https://juejin.cn/post/6860501233308794887#heading-31 *@param {array} Array Array to be sorted *@param {number} RadixBase // Base, sort in base 10, default base 10 *@returns {array} Returns the sorted array */
export function radixSort(array, radixBase = 10) {
  If the length of the array is less than 2, the array does not need to be sorted
  if (array.length < 2) {
    return array;
  }
  /** * This algorithm can also be modified to support sorting alphabetic characters. We first sort the numbers based only on the last significant bit, and in the next iteration we sort them based on the second significant bit (tens digit), then the third significant bit (hundreds digit), and so on. We continue this process until there are no significant bits to sort, which is why we need to know the minimum and maximum values in the array. * /
  const minValue = findMinValue(array); // Get the minimum array value
  const maxValue = findMaxValue(array); // Get the maximum value of the array
  // The current significant digit is sorted from the last (least significant) significant digit by default
  let significantDigit = 1;
  /** * Calculate the difference between the maximum and minimum significant bits * and divide with the significant bits. If the value is greater than or equal to 1, it represents the significant bits */ that are still to be sorted
  while ((maxValue - minValue) / significantDigit >= 1) { // Computes significant bits if (array Max - array min)/the number of current significant bits >= 1
    // console.log('radix sort for digit ' + significantDigit);
    // Call countingSortForRadix with the current valid bit to sort the array
    array = countingSortForRadix(array, radixBase, significantDigit, minValue);
    // console.log(array.join());
    // The current significant number is multiplied by the base, continuing the while loop for the base sort
    significantDigit *= radixBase;
  }
  return array;
}
Copy the code