java implements count sort and bucket sort instance code

java implements count sort and bucket sort instance code

directory

The difference between comparison and non-comparison

Common quicksort, merge sort, heap sort, bubble sort and so on belong to comparison sort. In the final result of sorting, the order of elements depends on their comparison. Each number must be compared with the others to determine its position.

In a sort like bubble sort, the problem size is n, and because it needs to compare n times, the average time complexity is O(n²). . In sorting, such as merge sort and quicksort, the problem size is reduced to logN times by divide and conquer, so the average time complexity is O(nlogn).

The advantage of comparative sorting is that you can sort data of all sizes, regardless of the distribution of the data. You could say that the comparison sort applies to the case where 1 cut requires sorting.

Count sort, radix sort, bucket sort belong to non-comparison sort. Non-comparative sorting is done by determining how many elements there should be before each element. For the array arr, calculate how many elements there are before arr[i], and only 1 determines the position of arr[i] in the sorted array.

Non-comparison sorting only needs to determine the number of existing elements before each element, and all 1 traversal can be solved. The algorithm time complexity O(n).

Non-comparison sorting has a time complexity base, but because non-comparison sorting requires space to determine the only position. Therefore, there is a definite requirement for data size and data distribution.

Count sorting

Counting sort applies to the range of data

Counting sort takes up a lot of space, and it only works when the data is relatively concentrated. Such data as [0~100], [10000~19999].

Process analysis

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

So you can simply place arr[i] in its output array. Suppose there are five Numbers less than arr[i], so arr[i] should be placed in the sixth position of the array.

Here are two implementations:

Algorithm Flow (1)

Three arrays are needed:

Array int[] arr = new int[]{4,3,6,3,5,1};

Auxiliary counting array int[] help = new int[ES73en-ES74en + 1]; // The array size is the maximum value of the array to be sorted minus the minimum value +1

Output array int[] res = new int[ES81en. length];

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

2. Instantiate the auxiliary counting array help. Each subscript in the help array corresponds to one element in arr, which is used to record the occurrence times of each element

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

4. Obtain the sorted array according to the help array, then res = [1,3,3,4,5,6]

public static int[] countSort1(int[] arr){
  if (arr == null || arr.length == 0) {
    return null;
  }
  
  int max = Integer.MIN_VALUE;
  int min = Integer.MAX_VALUE;
  
  // Find the maximum and minimum values in the array 
  for(int i = 0; i < arr.length; i++){
    max = Math.max(max, arr[i]);
    min = Math.min(min, arr[i]);
  }
  
  int help[] = new int[max];
  
  // Find the number of occurrences of each number 
  for(int i = 0; i < arr.length; i++){
    int mapPos = arr[i] - min;
    help[mapPos]++;
  }
  
  int index = 0;
  for(int i = 0; i < help.length; i++){
    while(help[i]-- > 0){
      arr[index++] = i+min;
    }
  }
  
  return arr;
}

Algorithm Flow (2)

Three arrays are needed:

Array int[] arr = new int[]{4,3,6,3,5,1};

Auxiliary counting array int[] help = new int[ES123en-ES124en + 1]; // The array size is the maximum value of the array to be sorted minus the minimum value +1

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 counting array help, which is used to record the number of elements before each element

3. Calculate the position of each number of arr in the sorted array, then help = [1,1,4,5,6,7];

4. Obtain the sorted array according to the help array, then res = [1,3,3,4,5,6]

public static int[] countSort2(int[] arr){
  int max = Integer.MIN_VALUE;
  int min = Integer.MAX_VALUE;
  
  // Find the maximum and minimum values in the array 
  for(int i = 0; i < arr.length; i++){
    max = Math.max(max, arr[i]);
    min = Math.min(min, arr[i]);
  }
  
  int[] help = new int[max - min + 1];
  
  // Find the number of occurrences of each number 
  for(int i = 0; i < arr.length; i++){
    int mapPos = arr[i] - min;
    help[mapPos]++;
  }
  
  // Calculate where each number should be in the sorted array 
  for(int i = 1; i < help.length; i++){
    help[i] = help[i-1] + help[i];
  }
  
  // According to the help Array sorting 
  int res[] = new int[arr.length];
  for(int i = 0; i < arr.length; i++){
    int post = --help[arr[i] - min];
    res[post] = arr[i];
  }
  
  return res;
}

Bucket sort

Corrigendum of network bucket sorting algorithm

In fact, the bucket sorting algorithm of the process in the network blog is count sort, not the standard bucket sort. The article in question:

Classic sorting algorithm - bucket sort Bucket sort

Bucket sorting algorithm

Sort algorithm bucket sort

The fastest and simplest sorting algorithm: bucket sort
Bucket sorting applies to the data range

Bucket sorting data can be used in the maximum minimum value is large, such as [9012197, 02398, 67689, 57835, 56102, 456].

However, bucket sorting requires the distribution of data to be uniform, otherwise the data may be concentrated in one bucket. For example [104,150,123,132,20000], 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: the array arr is divided into n subintervals of the same size (buckets), each subinterval is sorted separately, and finally merged.

Counting sort is a special case of bucket sort, and you can think of counting sort as if there were only one element in each bucket.

1. Find the maximum value max and the 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 (ES187en-ES188en)/ arr.length +1

3. Iterate through groups arr and calculate the bucket for each element arr[i]

4. Sort each bucket individually

5. Iterate through the bucket array, putting the sorted elements into the output array

public static void bucketSort(int[] arr){
  
  int max = Integer.MIN_VALUE;
  int min = Integer.MAX_VALUE;
  for(int i = 0; i < arr.length; i++){
    max = Math.max(max, arr[i]);
    min = Math.min(min, arr[i]);
  }
  
  // barrels 
  int bucketNum = (max - min) / arr.length + 1;
  ArrayList<ArrayList<Integer>> bucketArr = new ArrayList<>(bucketNum);
  for(int i = 0; i < bucketNum; i++){
    bucketArr.add(new ArrayList<Integer>());
  }
  
  // Put each element into the bucket 
  for(int i = 0; i < arr.length; i++){
    int num = (arr[i] - min) / (arr.length);
    bucketArr.get(num).add(arr[i]);
  }
  
  // Sort each bucket 
  for(int i = 0; i < bucketArr.size(); i++){
    Collections.sort(bucketArr.get(i));
  }
  
  System.out.println(bucketArr.toString());
  
}

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