Wechat search a search [Bigsai] continue to share for you

preface

In sorting data structures and algorithms, many of us are probably more familiar with bubble sort, quicksort and merge sort. Heap sorting, bucket sorting, counting rows, etc., may be unfamiliar, in fact, this is not complicated, bucket sorting is one of the simplest of all sorts. Good old iron, it’s one of the easiest. And bucket sort, count sort and radix sort have many similarities and origins. A comparative analysis will be conducted later. Keep an eye on it!

Bucket sorting idea

In fact, bucket sorting is important for the idea, rather than the implementation, bucket sorting from the literal meaning:

  • Buckets: Buckets, indicating that this sort puts data into buckets.
  • Buckets: Each bucket has a capacity. Buckets are containers with a certain volume, so there may be multiple elements in each bucket.
  • Buckets: On the whole, the whole sort prefers buckets to be more symmetrical, neither overflowing (too much) nor too little.

But what do buckets have to do with sorting? First of all, let’s talk about the idea of bucket sorting, baidu Baike said so

It works by dividing an array into a finite number of buckets. Each bucket is sorted individually (it is possible to use another sorting algorithm or to continue sorting using bucket sort recursively). Bucket sort is a kind of induction result of pigeon nest sort. Bucket sorting uses linear time (θ (n)) when the values in the array to be sorted are evenly distributed. But bucket sort is not comparison sort, and it is not affected by the O(n log n) lower bound.

To understand in plain English:

  • The sequence to be sorted is divided into several buckets, and the elements in each bucket are sorted individually.
  • The best time complexity is probably linear O(n), bucket sorting is not comparison-based sorting

Of course, bucket sort is a sort that trades space for time.

The final result must be from smallest to largest. Bucket sort uses the position of the bucket to perform a preliminary sort, placing the elements to be sorted into each bucket.

Generally, the elements to be sorted are evenly placed in the bucket according to the divisible method, such as 8, 5, 22, 15, 28, 9, 45, 42, 39, 19, 27, 47, 12. Assume that the bucket numbering rule is n/10. In this way, each element can be directly put into the corresponding bucket by divisible method. And all the buckets on the right are bigger than the buckets on the left!

When the bucket is just put into the bucket, the size of each bucket can be relatively determined, the right side is larger than the left side, but the bucket is still out of order, sorting each bucket respectively, and then according to the bucket sequence, bucket sequence to get a final sequence.

So that’s the idea of bucket sorting. If you use Java concrete implementation of the idea is also very simple: use the List[] type of collection array to represent the bucket, each List represents a bucket, the data according to the divisible value of the corresponding number of the collection directly into the set, and then sort it.

Analysis of bucket sorting algorithm

The above mentioned bucket sorting specific ideas, but you are not always feel psychological not so steadfast, this is over? Kind of weird, huh?

Bucket sorting does have a lot of differences, both the algorithm time complexity and the process of the whole algorithm, are not as fast sorting, merge these traditional to the real.

Time complexity analysis

What is the time complexity of bucket sorting?

Let’s say we have n numbers to sort. Divided into m buckets, if it’s evenly distributed so that on average each bucket has n over m elements. Firstly, I would like to emphasize that the time complexity of bucket sorting algorithm consists of two parts:

  • 1. Traversal processes each element, O(n) level normal traversal
  • 2. Total time complexity for reordering in each bucket

For the first part, I think you should understand the order of n that goes through at the end; In the second part, we can conduct the following analysis:

  • If the elements in the bucket are evenly distributedAssume that the sort algorithm used internally for each bucket is quicksort, then the time complexity in each bucket is(n/m) log(n/m). If there are m buckets, the time complexity is zerom * (n/m)log(n/m)=n (log n-log m).

Therefore, the time complexity of the final bucket sorting is:O(n)+O(n*(log n- log m))=O(n+n*(log n -log m))M is the number of buckets. Sometimes we’ll write order n plus c, where c is n times log n minus log m;

Here, if you go to the limit casen=mAt the right time. You can make sure that you don’t have to sort things in buckets, that you don’t have to sort things in buckets to get the order of O(n), and of course that’s counting sort, and we’ll talk about counting sort later.

Bucket sort applies

Bucket sort and like regular sort there is no limit, bucket sort is quite limited. Because the number and size of buckets are artificially set by us. And each bucket should avoid empty bucket situation. Therefore, when we use bucket sorting, we need to treat the sorting sequence requirements of partial uniformity, and also require the design of bucket to take into account efficiency and space.

Is the sequence to be sorted uniform? What if I’m not even?Will be like this:This is equivalent to using only a small number of buckets in effect, and then looking at the time complexity of bucket sorting:O(n+n*(log n -log m))M goes one, log m goes zeroO(n+nlogn)In terms of rankO(nlogn)Take a look at this. It’s the same as not using buckets. It’s the time complexity of fast sorting (or other sorts).

Well, can’t I get 100,000 barrels?No, really no, if 100,000 barrels, look what happens:This is less than 100 numbers, you’re using 100,000 Spaces to map one to one, you’re wasting space, you’re traversing the order of n even though it’s 100,000 times more than 100O(nlogn)It’s a lot bigger. It’s a double whammy.

So now you see the point: the numbers have to be relatively evenly distributed, and the number of barrels has to be reasonably designed. Anyway, bucket sort is a sort that trades space for time. In designing bucket sorting, you need to know the upper and lower bounds of input data, see the distribution of data, and then consider whether to use bucket sorting, of course, if you can use good bucket sorting, efficiency is very high!

Implement a bucket sort

Here with Java to give you a bucket sort. The assumed sequence is 1 8 7 44 42 46 38 34 33 17 15 16 27 28 24; We chose 5 buckets for bucket sorting.

import java.util.ArrayList;
import java.util.List;
// Wechat official account: Bigsai
public class test3 {
	public static void main(String[] args) {
		int a[]= {1.8.7.44.42.46.38.34.33.17.15.16.27.28.24};
		List[] buckets=new ArrayList[5];
		for(int i=0; i<buckets.length; i++)/ / initialization
		{
			buckets[i]=new ArrayList<Integer>();
		}
		for(int i=0; i<a.length; i++)// Put the sequence to be sorted into the bucket
		{
			int index=a[i]/10;// The corresponding bucket number
			buckets[index].add(a[i]);
		}
		for(int i=0; i<buckets.length; i++)// Sort within each bucket (use the system's own quick sorting)
		{
			buckets[i].sort(null);
			for(int j=0; j<buckets[i].size(); j++)// Print it out
			{
				System.out.print(buckets[i].get(j)+""); }}}}Copy the code

The printed result is:

conclusion

At this point, bucket sort is finished, of course, this article may have a place to say bad or have loopholes also please big guy pointed out, behind will also explain counting sort, radix sort and summed up the three!

The author’s wechat official account: Bigsai is an interesting young man. He often does some interesting projects and activities with everyone through his official account. Welcome to follow him. If help, please point a zan Zan support!