The beauty of JavaScript data structures and algorithms – bucket sort, count sort, radix sort

1. Introduction

The algorithm is king.

Want to learn the front end, first practice good internal skills, only deep internal skills, the front road will go further.

The author wrote the beauty of JavaScript data structure and algorithm series with the language is JavaScript, aimed at the introduction of data structure and algorithm and convenient later review.

Counting sort, bucket sort, and radix sort are compared together because they all have an average time complexity of O(n).

Because the time complexity of these three sorting algorithms is Linear, we call this kind of sorting algorithm Linear sort.

The main reason why linear time complexity can be achieved is that these three algorithms are not comparison-based sorting algorithms and do not involve comparison operations between elements.

Also, please read the following with a question: How do you rank a million users by age?

2. Bucket Sort

Bucket sort is an upgraded version of counting sort and also uses the idea of divide-and-conquer.

thought

• The data to be sorted is sorted into a finite number of ordered buckets.
• The data in each bucket is sorted separately (usually by insert sort or quicksort).
• After the bucket is sorted, the data in each bucket is taken out in sequence to form an orderly sequence.

Such as:

Bucket sorting makes use of the mapping relation of function, and the key of efficiency lies in the determination of the mapping function.

To make bucket sorting efficient, we need to do two things:

• Increase the number of barrels as much as extra space is available.
• The mapping function used can evenly distribute the N input data into K buckets.

The core of bucket sorting is how to evenly distribute elements to each bucket. Reasonable allocation will greatly improve the efficiency of sorting.

implementation

/ / bucket sorting
const bucketSort = (array, bucketSize) = > {
  if (array.length === 0) {
    return array;
  }

  console.time('Bucket Sort time');
  let i = 0;
  let minValue = array[0];
  let maxValue = array[0];
  for (i = 1; i < array.length; i++) {
    if (array[i] < minValue) {
      minValue = array[i]; // The minimum value of input data
    } else if (array[i] > maxValue) {
      maxValue = array[i]; // The maximum value of the input data}}// Initialize the bucket
  const DEFAULT_BUCKET_SIZE = 5; // Set the default number of buckets to 5
  bucketSize = bucketSize || DEFAULT_BUCKET_SIZE;
  const bucketCount = Math.floor((maxValue - minValue) / bucketSize) + 1;
  const buckets = new Array(bucketCount);
  for (i = 0; i < buckets.length; i++) {
    buckets[i] = [];
  }

  // Allocate data to buckets using mapping functions
  for (i = 0; i < array.length; i++) {
    buckets[Math.floor((array[i] - minValue) / bucketSize)].push(array[i]);
  }

  array.length = 0;
  for (i = 0; i < buckets.length; i++) {
    quickSort(buckets[i]); // Sort each bucket, using quicksort
    for (var j = 0; j < buckets[i].length; j++) { array.push(buckets[i][j]); }}console.timeEnd('Bucket Sort time');

  return array;
};

// Quicksort
const quickSort = (arr, left, right) = > {
	let len = arr.length,
		partitionIndex;
	left = typeofleft ! ='number' ? 0 : left;
	right = typeofright ! ='number' ? len - 1 : right;

	if (left < right) {
		partitionIndex = partition(arr, left, right);
		quickSort(arr, left, partitionIndex - 1);
		quickSort(arr, partitionIndex + 1, right);
	}
	return arr;
};

const partition = (arr, left, right) = > {
	// Partition operations
	let pivot = left, // Set the pivot value
		index = pivot + 1;
	for (let i = index; i <= right; i++) {
		if (arr[i] < arr[pivot]) {
			swap(arr, i, index);
			index++;
		}
	}
	swap(arr, pivot, index - 1);
	return index - 1;
};

const swap = (arr, i, j) = > {
	let temp = arr[i];
	arr[i] = arr[j];
	arr[j] = temp;
};
Copy the code

test

const array = [4.6.8.5.9.1.2.5.3.2];
console.log('original array:, array);
const newArr = bucketSort(array);
console.log('newArr:', newArr);
// Original array: [4, 6, 8, 5, 9, 1, 2, 5, 3, 2]
// Heap sort time: 0.133056640625ms
// newArr: [1, 2, 2, 3, 4, 5, 5, 6, 8, 9]
Copy the code

Analysis of the

• First, is bucket sort an in-place sort algorithm?

Because of the space complexity of bucket sorting, that is, the memory consumption is O(n), it is not in place sorting algorithm.

• Second, is bucket sorting a stable sorting algorithm?

Depending on how each bucket is sorted, for example, quicksort is unstable, merge is stable.

• Third, what is the time complexity of bucket sorting?

Because bucket sorting can be done in many ways, it has a significant impact on bucket sorting time complexity. Therefore, the time complexity of bucket sorting can be varied.

Overall best case: when the input data is evenly distributed to each bucket. Worst case: when the input data is allocated to the same bucket.

The internal sort of the bucket is quicksort:

If we have n numbers to sort, and we divide them evenly into m buckets, each bucket will have k =n/m elements. Each bucket uses internal quicksort and the time complexity is O(k x logk). The time complexity of sorting m buckets is O(m * k * logk). Since k = n/m, the time complexity of sorting m buckets is O(n*log(n/m)). When the number of buckets m is close to the number of data n, log(n/m) is a very small constant, and the time complexity of bucket sorting is close to O(n).

Best case: T(n) = O(n). When the input data can be evenly distributed to each bucket. Worst case: T(n) = O(nlogn). When the input data is allocated to the same bucket. Average case: T(n) = O(n).

The optimal linear time for bucket sorting is O(n). The time complexity of bucket sorting depends on the time complexity of sorting data between buckets, because the time complexity of all other parts is O(n). Obviously, the smaller the bucket, the less data there is between the buckets, and the less time it takes to sort. But the corresponding space consumption will increase.

Applicable scenario

• Bucket sort is suitable for external sort.
• External sort means that the data is stored on an external disk with a large amount of data, but the memory is limited. Therefore, the entire data cannot be loaded into the memory.

animation

3. Counting Sort

thought

• Find the largest and smallest elements in the array to be sorted.
• Count the number of occurrences of each element of the array with the value I into the i-th entry of the new array countArr.
• All counts are added up (starting with the first element in countArr, each term is added to the previous one).
• Reverse populating the target array: Place each element I in the first countArr[I] of the new array, subtracting countArr[I] by 1 for each element.

The key is to understand what happens when you finally reverse populate.

Conditions of use

• It can only be used in scenarios where the data range is small. If the data range K is much larger than the data to be sorted n, it is not suitable for counting sort.
• Counting sort can only sort non-negative integers. Other types need to be converted to non-negative integers without changing their relative sizes.
• For example, if the test score is accurate to the last decimal place, you need to multiply all the scores by 10 to round them up.

implementation

Method one:

const countingSort = array= > {
	let len = array.length,
		result = [],
		countArr = [],
		min = (max = array[0]);
	console.time('Counting sort time');
	for (let i = 0; i < len; i++) {
		// Get the minimum and maximum values
		min = min <= array[i] ? min : array[i];
		max = max >= array[i] ? max : array[i];
		countArr[array[i]] = countArr[array[i]] ? countArr[array[i]] + 1 : 1;
	}
	console.log('countArr :', countArr);
	// Add the count term by term from minimum -> maximum
	for (let j = min; j < max; j++) {
		countArr[j + 1] = (countArr[j + 1] | |0) + (countArr[j] || 0);
	}
	console.log('countArr 2:', countArr);
	// in countArr, the subscript is array value, and the data is array number of occurrences; Reverse populates the data into the Result data
	for (let k = len - 1; k >= 0; k--) {
		// result[location] = array data
		result[countArr[array[k]] - 1] = array[k];
		// Reduce the count stored in the countArr array
		countArr[array[k]]--;
		// console.log("array[k]:", array[k], 'countArr[array[k]] :', countArr[array[k]],)
		console.log('result:', result);
	}
	console.timeEnd('Counting sort time');
	return result;
};
Copy the code

test

const array = [2.2.3.8.7.1.2.2.2.7.3.9.8.2.1.4.2.4.6.9.2];
console.log('Original array:', array);
const newArr = countingSort(array);
console.log('newArr: ', newArr);
/ / the original array: [2, 2, 3, 8, 7, 1, 2, 2, 2, 7, 3, 9, 8, 2, 1, 4, 2, 4, 6, 9, 2)
// Count sort time: 5.6708984375ms
// newArr: [1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 4, 4, 6, 7, 7, 8, 8, 9, 9]
Copy the code

Method 2:

const countingSort2 = (arr, maxValue) = > {
	console.time('Counting sort time');
	maxValue = maxValue || arr.length;
	let bucket = new Array(maxValue + 1),
		sortedIndex = 0;
	(arrLen = arr.length), (bucketLen = maxValue + 1);

	for (let i = 0; i < arrLen; i++) {
		if(! bucket[arr[i]]) { bucket[arr[i]] =0;
		}
		bucket[arr[i]]++;
	}

	for (let j = 0; j < bucketLen; j++) {
		while (bucket[j] > 0) { arr[sortedIndex++] = j; bucket[j]--; }}console.timeEnd('Counting sort time');
	return arr;
};
Copy the code

test

const array2 = [2.2.3.8.7.1.2.2.2.7.3.9.8.2.1.4.2.4.6.9.2];
console.log('Primitive Array2:', array2);
const newArr2 = countingSort2(array2, 21);
console.log('newArr2: ', newArr2);
/ / the original array: [2, 2, 3, 8, 7, 1, 2, 2, 2, 7, 3, 9, 8, 2, 1, 4, 2, 4, 6, 9, 2)
// Count sort time: 0.043212890625ms
// newArr: [1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 4, 4, 6, 7, 7, 8, 8, 9, 9]
Copy the code

example

You can think of counting sort as a special case of bucket sort.

When the n numbers that we want to sort are on a small scale, for example, the maximum is k, we can divide the data into k buckets. The data values in each bucket are the same, saving the sorting time in the bucket.

We all went through the college entrance examination, the high test score system. Do you remember? When we check the score, the system will show us our score and the rank of our province. If your province has half a million examinees, how do you get the ranking through quick ranking?

• The full score of examinees is 900 and the minimum score is 0. This data range is very small, so we can divide it into 901 buckets with scores ranging from 0 to 900.
• According to the scores of the examinees, we divided the 500,000 examinees into these 901 buckets. The data in the bucket are all examinees with the same score, so there is no need to sort.
• We just need to scan each bucket in turn, output the examinees in the bucket in turn into an array, and achieve a sort of 500,000 examinees.
• Because only scan traversal is involved, the time complexity is O(n).

Analysis of the

• First, is counting sort an in-place sort algorithm? Because the spatial complexity of counting sort is O(k), where K is the number of buckets, it is not an in-place sorting algorithm.
• Second, is counting sort a stable sorting algorithm? Counting sort does not change the relative order of the same elements, so it is a stable sorting algorithm.
• Third, what is the time complexity of counting sort? Best case: T(n) = O(n + K) Worst case: T(n) = O(n + K) Average case: T(n) = O(k) K: number of buckets.

animation

4. Radix Sort

thought

Radix sort is a kind of non-comparative integer sort algorithm. Its principle is to cut the integers into different numbers according to the number of digits, and then compare them according to each number.

Since integers can also represent strings (such as names or dates) and floating-point numbers in a particular format, radix sort is not restricted to integers.

example

Suppose we have 100,000 mobile phone numbers and we want to sort them from smallest to largest. What’s a quick way to sort them?

If you want to compare the size of two mobile phone numbers a and B, if a is already larger than B in the first few digits, you don’t need to look at the next few digits. So it’s based on bits.

Can bucket sort, count sort come in handy? The 11-digit range of mobile phone numbers is too large to use either sorting algorithm. Is there an O(n) algorithm for this sorting problem? Yes, it’s radix sort.

Conditions of use

• Requires that the data be split independentlypositionTo compare;
• There is a progressive relationship between bits. If the high position of data A is larger than that of data B, there is no need to compare the remaining positions.
• The data range of each bit should not be too large, and linear sorting should be possible, otherwise the time complexity of radix sorting cannot reach O(n).

plan

There are two implementations of sorting from the highest or lowest level by priority:

• MSD: by high for the basement, sort by k1 group, first recorded in the same group, key k1, equal to each sort by k2 is divided into subgroups, later, on the back of the key to continue this sort of grouping, until according to the second key kd to various subgroups sorted, connect each again, then get an ordered sequence. MSD mode is suitable for sequences with many bits.
• LSD: From the low position as the base, sort from kd first, then sort kD-1, and repeat successively until an ordered sequence is obtained after sorting k1. LSD is suitable for sequences with few bits.

implementation

/** * name: cardinality sort * @param array array to sort * @param Max maximum number */
const radixSort = (array, max) = > {
	console.time('Counting sort time');
	const buckets = [];
	let unit = 10,
		base = 1;
	for (let i = 0; i < max; i++, base *= 10, unit *= 10) {
		for (let j = 0; j < array.length; j++) {
			let index = ~~((array[j] % unit) / base); // Filter out the ones, tens, and so on
			if (buckets[index] == null) {
				buckets[index] = []; // Initialize the bucket
			}
			buckets[index].push(array[j]); // Add data to different buckets
		}
		let pos = 0,
			value;
		for (let j = 0, length = buckets.length; j < length; j++) {
			if(buckets[j] ! =null) {
				while((value = buckets[j].shift()) ! =null) {
					array[pos++] = value; // Retrieve data from different buckets one by one to prepare for the next round of ranking. Since elements near the bottom of the bucket rank higher, they are retrieved from the bottom of the bucket first}}}}console.timeEnd('Counting sort time');
	return array;
};
Copy the code

test

const array = [3.44.38.5.47.15.36.26.27.2.46.4.19.50.48];
console.log('original array:, array);
const newArr = radixSort(array, 2);
console.log('newArr:', newArr);
// Original array: [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]
// Heap sort time: 0.064208984375ms
// newArr: [2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]
Copy the code

Analysis of the

• First, is radix sort an in place sort algorithm? Because the spatial complexity of counting sort is O(n + K), it is not an in-place sorting algorithm.

• Second, is radix sort a stable sorting algorithm? Radix sort does not change the relative order of the same elements, so it is a stable sorting algorithm.

• Third, what is the time complexity of radix sort? Best case: T(n) = O(n * k) Worst case: T(n) = O(n * k) Average case: T(n) = O(n * k) K is the maximum value to be sorted.

animation

LSD radix sort GIF demo:

5. Answer the opening paragraph

Take a look back at the opening question: How do you rank a million users by age?

You might say, well, I can just merge and sort in the last video. Yes, they can do the job, but the minimum time complexity is O(nlogn).

Is there a faster way to sort it? The following are the reference answers.

• In effect, ranking one million users by age is akin to ranking half a million test-takers by grade.
• We assume that the range of ages is as low as 1 year and as high as 120 years.
• We can iterate over the 1 million users, divide them into 120 buckets by age, and then iterate over the elements in each of those 120 buckets in order.
• So you get a million users sorted by age.

6. Complexity comparison

Radix sort vs counting sort vs bucket sort

There are two ways to sort radix:

• MSD sorts from the top
• LSD sorts from the low end

These three sorting algorithms all use the concept of buckets, but there are obvious differences in the way buckets are used:

• Radix sort: buckets are allocated according to each digit of the key value;
• Counting sort: each bucket stores a single key;
• Bucket sorting: Each bucket stores a range of values;

Complexity contrast

The name of the	On average,	The best	The worst	space	The stability of	The sorting way
Bucket sort	O(n + k)	O(n + k)	O(n2)	O(n + k)	Yes	Out-place
Count sorting	O(n + k)	O(n + k)	O(n + k)	O(k)	Yes	Out-place
Radix sort	O(n * k)	O(n * k)	O(n * k)	O(n + k)	Yes	Out-place

N: Data scale

The time complexity of bucket sort can vary, depending on the sort within the bucket.

7. Algorithm visualization tool

• Algorithm-visualizer is an interactive online platform that allows you to visualize algorithms in your code, as well as the process of code execution. The effect is shown below.

It aims to reveal the mechanism behind the algorithm through interactive visual execution.

• Algorithm visualization source visualgo.net/en The effect is shown below.

  

• www.ee.ryerson.ca

• Visual representation of variables and operations in Illustrated – Algorithms enhances the control flow and actual source code. You can quickly move forward and backward to get a close look at how the algorithm works.

8. Series of articles

A series of articles on the beauty of JavaScript data structures and algorithms.

The title	link
Time and space complexity	Github.com/biaochenxuy…
Linear tables (arrays, linked lists, stacks, queues)	Github.com/biaochenxuy…
Implementing a front-end route, how to implement browser forward and backward?	Github.com/biaochenxuy…
Stack and heap memory, shallow copy and deep copy	Github.com/biaochenxuy…
recursive	Github.com/biaochenxuy…
Nonlinear tables (tree, heap)	Github.com/biaochenxuy…
Bubble sort, select sort, insert sort	Github.com/biaochenxuy…
Merge sort, quicksort, Hill sort, heap sort	Github.com/biaochenxuy…
Count sort, bucket sort, radix sort	Github.com/biaochenxuy…
Top 10 classic rankings	Github.com/biaochenxuy…
Highly recommended GitHub data structures and algorithms project worth front-end learning	Github.com/biaochenxuy…

If there is any mistake or not precise place, please be sure to give correction, thank you very much.

9. The last

All the code and test cases in this article have been posted on my GitHub.

Think it works? Like to collect, by the way point like it, your support is my biggest encouragement!

Reference article:

• Rookie tutorial – algorithm series
• Linear sorting: How to sort 1 million user data by age?
• Top 10 Classic Sorting Algorithms
• JS can be used to get all sorts of algorithms