Let’s start with counting sort

Counting sort is a sorting algorithm that is not based on element comparison, but transforms the elements to be sorted into the index value of counting array, thus indirectly making the array to be sorted sequential.

Counting sort is generally implemented in two forms: auxiliary array – based and bucket – based.

Based on auxiliary arrays

The whole process consists of three arrays: array A to sort, array B to count, and array C to output.

In simple terms, is through A of the statistics to sort an array element distribution histogram of different values, to generate counter array B, and calculate the count array B prefix and step (this operation can be seen as computing the position of each element in A sorted array information), the last element by reverse circulation corresponding to assign values to the output array in C, C output array is sorted result finally.

Bucket based sorting

Bucket sorting is used to maintain stability, because the elements in each bucket are sorted in a queue structure, and the order of the elements can be maintained.

Main steps:

  1. Creates a specified number of buckets by the difference between the element’s maximum and minimum keys, and creates a queue in each bucket.
  2. Iterate through the arrays to be sorted in order, placing them in the queue of the corresponding bucket.
  3. The queue in each bucket is output back to the original array in sequence.

Counting sort deficiencies

As you can see, the length of the auxiliary array and the number of buckets are determined by the maximum and minimum values. If the difference between the two is large and the array to be sorted is small, then the auxiliary array or bucket will be wasted.

Radix sort

Radix sort improved count sorting, in simple terms, radix sort algorithm is cut an integer or a string into different Numbers or characters, and then according to the corresponding position of the number or character comparison respectively, so it can cut the number of auxiliary array or barrel to a smaller value, after several rounds of sorting to get the final sorting result.

For example, for the decimal comparison below, you only need 10 buckets, but make sure that each bucket can hold all the elements.

Stage 1: Put the element into the bucket for the units digit.

Stage 2: Place elements in buckets for tens of digits.

Stage 3: Place elements in buckets for hundreds.

Finally, the sorting result is output according to bucket order.

Bucket sort

Bucket sort is one of the methods to improve counting sort. The basic idea is to allocate the array to be sorted into several buckets, and then sort within each bucket separately. The sort within the bucket can use different algorithms, such as insertion sort or quick sort, belonging to the divide-and-conquer method. After each bucket is sorted, the ordered sequence in each bucket is finally taken out, that is, the complete sorting result is obtained.

The maximum element and minimum element of the array to be sorted are 19 and 1 respectively, so the total range can be defined as [0,19]. Assuming that four buckets are used, the range of buckets is [0,4][5,9][10,14][15,19] respectively. As you can see, the number of buckets can be kept within a very small range, and the size of buckets can be dynamically expanded.

Put the element into the bucket according to the value.

Output the elements in bucket order to get the sorting result.

conclusion

  • Radix sort and bucket sort can be thought of as generalized versions of counting sort, using some measures to optimize the sorting process.
  • In bucket sorting, when the number of buckets reaches the maximum (max-min+1), it becomes counting sort, so counting sort is a special case of bucket sorting.
  • Radix sort can be thought of as multi-round bucket sort, in terms of significant bits, each significant bit carries out a round of bucket sort.
  • When maximum is used as radix, radix sort degenerates into counting sort.

————- Recommended reading ————

Summary of my open Source projects (Machine & Deep Learning, NLP, Network IO, AIML, mysql protocol, Chatbot)

Why to write “Analysis of Tomcat Kernel Design”

2018 summary data structure algorithms

2018 Summary machine learning

2018 Summary Java in Depth

2018 Summary of natural language processing

2018 Summary of deep learning

2018 summary JDK source code

2018 Summary Java concurrency Core

2018 summary reading passage


Talk to me, ask me questions:

Welcome to: