Java implementation of counting sorting and bucket sorting instance code

Java implementation of counting sorting and bucket sorting instance code

catalogue

The difference between comparison and non comparison

Common quick sort, merge sort, heap sort and bubble sort belong to comparative sort. In the final result of sorting, the order between elements depends on the comparison between them. Each number must be compared with other numbers to determine its position.

In bubble sort, the problem scale is n, and because it needs to be compared n times, the average time complexity is O (n) ²)。 In sorting such as merge sort and quick sort, the problem scale is reduced to logn times by divide and conquer, so the time complexity is O (nlogn) on average.

The advantage of comparative sorting is that it is suitable for data of all sizes and does not care about the distribution of data. It can be said that comparative sorting is applicable to all situations that need sorting.

Count sort, cardinality sort and bucket sort belong to non comparison sort. Non comparative sorting is to sort by determining how many elements should be before each element. For array arr, calculate the number of elements before arr [i], and uniquely determine the position of arr [i] in the sorted array.

Non comparative sorting can be solved by determining the number of existing elements before each element, and all traversals can be solved at one time. Algorithm time complexity O (n).

The time complexity of non comparative sorting is low, but it takes up space to determine the unique location. Therefore, there are certain requirements for data scale and data distribution.

Count sort

Applicable data range of count sorting

Counting sorting takes up a lot of space, and it is only applicable to the case of data concentration. Data such as [0 ~ 100] and [10000 ~ 19999].

process analysis

The basic idea of counting sorting is to determine the number of elements less than arr [i] for each input element arr [i].

So you can put arr [i] directly in its output array. Suppose there are five numbers less than arr [i], so arr [i] should be placed at the sixth position of the array.

Two implementations are given below:

Algorithm flow (1)

Three arrays are required:

Array to be sorted int [] arr = New Int [] {4,3,6,5,1};

Auxiliary count array int [] help = New Int [max - min + 1]// The size of the array is the maximum value minus the minimum value + 1 in the array to be sorted

Output array int [] res = New Int [arr.length];

1. Find the maximum value max = 6 and the minimum value min = 1 of the array to be sorted

2. Instantiate the auxiliary count array help. Each subscript in the help array corresponds to an element in the arr. help is used to record the number of occurrences of each element

3. Calculate the position of each element in arr in help = arr [i] - min, and help = [1,2,1,1]; (3 appears twice, 2 does not appear)

4. Get the sorted array according to the help array, and res = [1,4,6]

Algorithm flow (2)

Three arrays are required:

Array to be sorted int [] arr = New Int [] {4,1};

Auxiliary count array int [] help = New Int [max - min + 1]// The size of the array is the maximum value minus the minimum value + 1 in the array to be sorted

Output array int [] res = New Int [arr.length];

1. Find the maximum value max = 6 and the minimum value min = 1 of the array to be sorted

2. Instantiate the auxiliary count array help, which is used to record the number of elements before each element

3. Calculate the position that each number of arr should be in the array after sorting. At this time, help = [1,7];

4. Get the sorted array according to the help array. At this time, res = [1,6]

Bucket sorting

Corrigendum to network bucket sorting algorithm

In fact, the bucket sorting algorithm of processes in each blog post on the network is counting sorting, not standard bucket sorting. Problematic articles:

Classic sorting algorithm bucket sort

Bucket sorting algorithm

Bucket sorting of sorting algorithm

The fastest and simplest sorting algorithm: bucket sorting bucket sorting applicable data range

Bucket sorting can be used for data with large difference between maximum and minimum values, such as [901219702398676895783556102456].

However, bucket sorting requires that the data must be evenly distributed, otherwise the data may be concentrated in one bucket. For example [10415012313220000], this data will cause the first four numbers to be concentrated in the same bucket. Causes bucket sorting to fail.

process analysis

The basic idea of bucket sorting is to divide the array arr into n sub intervals (buckets) of the same size, sort each sub interval separately, and finally merge.

Counting sorting is a special case of bucket sorting, which can be regarded as the case where there is only one element in each bucket.

1. Find out the maximum value Max and minimum value min in the array to be sorted

2. We use the dynamic array ArrayList as the bucket, and the elements in the bucket are also stored in ArrayList. The number of barrels is (max min) / arr.length + 1

3. Traverse the array arr and calculate the bucket of each element arr [i]

4. Each bucket is sorted separately

5. Traverse the bucket array and put the sorted elements into the output array

Thank you for reading, hope to help you, thank you for your support to this site!