This is the ninth day of my participation in the August More text Challenge. For details, check out the top 10 classic Sorting algorithms of the August More Text Challenge

Ten sorting algorithms – bubble sort

Ten sorting algorithms – selection sort

Ten sorting algorithms – insertion sort

Ten sorting algorithms – Hill sort

Ten sorting algorithms – merge sort

Ten sorting algorithms – quick sort

Ten sort algorithms – heap sort

Ten sorting algorithms – counting sort

Ten sort algorithms – radix sort

Bucket sort

Bucket sort is an upgrade of counting sort. Counting sort can be viewed as each bucket only stores the same elements, while bucket sort can be viewed as each bucket stores a certain range of elements. Through some mapping relationship of functions, the elements in the array to be sorted are mapped to the corresponding buckets. The elements in each bucket are sorted (it is possible to use another sorting algorithm or continue using bucket sort recursively), and the elements in the non-empty buckets are finally placed one by one into the original sequence.

Bucket sorting needs to ensure that elements are evenly distributed. Otherwise, bucket sorting fails when all data is concentrated in the same bucket.

Code implementation

  1. Find the maximum value Max and minimum value min in the array, you can determine the array range min~ Max

  2. The number of buckets is determined based on the data range

    • If the number of buckets is too small, bucket sorting fails
    • If the number of buckets is too large, some buckets may have no data and waste space

    So it’s up to us to determine the number of buckets, but try to distribute the elements equally in each bucket, so here’s a way to do it

    (Max - min)/ how many different values can be placed in each bucket +1

  3. The interval for determining buckets is generally divided according to the number of buckets (maximum – minimum), and is closed left and opened right

public class BucketSort { public static final int[] ARRAY = {35, 23, 48, 9, 16, 24, 5, 11, 32, 17}; /** * @param bucketSize specifies the number of different values that can be placed in a bucket, that is, the type of the value * for example, if bucketSize ==5, the bucket can hold {1,2,3,4,5}, * but there is no limit to the size, 3 */ public static List<Integer> sort(List<Integer> array, int bucketSize) { if (array == null || array.size() < 2) return array; int max = array.get(0), min = array.get(0); For (int I = 0; i < array.size(); i++) { if (array.get(i) > max) max = array.get(i); if (array.get(i) < min) min = array.get(i); } // Number of buckets to obtain int bucketCount = (max-min)/bucketSize + 1; // Build the bucket and initialize List<ArrayList<Integer>> bucketArr = new ArrayList<>(bucketCount); List<Integer> resultArr = new ArrayList<>(); for (int i = 0; i < bucketCount; i++) { bucketArr.add(new ArrayList<>()); } for (int I = 0; i < array.size(); Get ((array.get(I) -min)/bucketSize).add(array.get(I)); } for (int i = 0; i < bucketCount; i++) { if (bucketSize == 1) { for (int j = 0; j < bucketArr.get(i).size(); j++) resultArr.add(bucketArr.get(i).get(j)); } else { if (bucketCount == 1) bucketSize--; List<Integer> temp = sort(bucketarr.get (I), bucketSize); for (int j = 0; j < temp.size(); j++) resultArr.add(temp.get(j)); } } return resultArr; } public static void print(List<Integer> array) { for (int i : array) { System.out.print(i + " "); } System.out.println(""); } public static void main(String[] args) { print(Arrays.stream(ARRAY).boxed().collect(Collectors.toList())); System.out.println("============================================"); print(sort(Arrays.stream(ARRAY).boxed().collect(Collectors.toList()), 2)); }}Copy the code

Time complexity

The bucket sort algorithm traverses the original array twice, and the operation amount is 2N. Finally, the operation amount of traversing the bucket to output the sorting result is N, and the operation amount of initializing the bucket is M.

For bucket sorting, different sorting algorithms have different complexity. The complexity of bubble sorting algorithm is O(N^2), and the complexity of heap sorting and merge sorting algorithm is O(N logn). We calculate the sorting algorithm with the complexity of O(N logn), and the computation is N/M * log(N/M) * M

The final calculation is 3N+M+N/M * log(N/M) * M, which is 3N+M+N(logN-logM), and the time complexity is O(N+M+N(logN-logM)).

Reference: bucket sort algorithm in detail

Algorithm stability

If a stable sorting algorithm is selected when sorting each bucket, the position of the same element will not change after sorting. Therefore, the bucket sorting algorithm is a stable sorting algorithm.