Learn the algorithm from the watermelon brothers
Eldest brother: I simply tell you next, you have learned so much sort, estimate a look to understand. Radix sort, is a radix “bucket” sort, his sort idea is like this: first to the size of the one digit to sort the data, then to the size of the ten digit to most sort, and then to the size of the hundreds……
At the end, you have an ordered set of elements. However, when he sorted by a certain number, he used “buckets” to sort, the basic principle is to put the numbers with the same number (ten, hundreds, etc.) into the same bucket. Let me just give you an example, just to make sure you understand it.
For example, we now want to sort this set of elements:
Since we are sorting by some number of each number, which ranges from 0 to 9, we need 10 buckets.
The first time, we sorted the numbers in units digit order and put the numbers with the same units digit into the bucket. The result is as follows:
And then they took them out in the order from bucket 0 to bucket 9, and the result was as follows
The ones digit sort is done.
The second time, in order of ten digits, the result is as follows:
Take it out and put it back:
The result is an ordered set of elements. If there are hundreds of digits in the element, the worst case, according to the hundreds of digits to repeat the row again.
Second brother: That I want to ask next, why want to start from one digit sort? Can we sort directly from the highest digit? If you sort from the highest digit, if the highest digit is greater than the other digit, then this digit must be greater than the other digit, so it doesn’t have to be in the second highest digit. In that case, wouldn’t it be faster?
Eldest brother: That’s a quick brain. Yes, it’s possible to sort by the highest digit, and as you said, sorting by the highest digit reduces the number of comparisons between data. But we still don’t recommend sorting by highest place, because it has a fatal flaw.
Boss: Let’s go back to the previous example, where we sort by the highest place while looking for this fatal flaw. The array looks like this (the order of the elements has changed a bit) :
First pass: the highest ten digit sort, the result is as follows (some unused buckets are omitted):
Obviously, is not in the barrel of a bucket number, their size order is known, that is, on the right side of the barrel number must be larger than the left bucket number, all in the next single sort, we only need to “parts” separate sorting, each a small part is similar to the original problem of a child, does can use recursive form to deal with.
Finally summarize, you can complete the sorting:
Is this method can reduce the number of times but please note that in each of the small number of sorting, we also need 10 barrels to sort them, the final result, each of the different value elements will occupy a “bucket”, if you have 1000 elements, and 1000 elements are different value, So to sort from the highest to the lowest, you need 1,000 buckets.
Not only does it cost a lot of space, but it also looks like a departure from the original idea of radix sort (” departure “is a personal word). So, we usually use the order from the lowest to the highest.
About cardinal sort, there are the following questions, you might as well think about it?
1, radix sort is a sort algorithm with space for time, the larger the amount of data, the larger the extra space?
My idea: I think radix sort is not a kind of time space sort, that is, the larger the amount of data, the larger the extra space is not. It is perfectly possible to point to an element when putting it into a bucket, which means that only the original bucket counts as extra space.
2. Extra space is not the reason for limiting the speed of radix sort, so why is radix sort not as fast as quicksort?
Base time complexity is O (n), but he is ignoring the constant terms, namely, the actual sorting for kn is constant (k), in the process of the actual sorting, however, the constant k is very big, this will greatly affect the practical sort time, although such as quick sort is nlogn, but it in front of the constant term is relatively small, The impact is relatively small.
It should also be noted that radix sort is not slower than quicksort, depending on the situation (don’t let the title bother you). Moreover, the larger the data volume, the greater the advantage of radix sort.
3. One might ask, having said all that, is radix sort faster or quicksort faster?
To answer this question, I can only suggest that you roll out a few lines of code for different scenarios and test them yourself.
If you ask me which sort is actually used more, I’m going to say quicksort.
That’s the end of the article, if you have any other ideas, welcome backstage harassment.
If you find this article inspiring, in order for more people to see this article, please
1, like, so that more people can see this content (collection does not like, are playing rogue -_-)
Pay attention to me and column, let us become a long-term relationship
3. Pay attention to the public account “Helpless and painful code farmer”, mainly write articles like algorithm and computer foundation, which has more than 100 original articles, I also share a lot of videos, books resources, and development tools, welcome your attention, the first time to read my article.
