ソートをカウントするためのJavaプログラム

カウントソートは、個別のキー値を持つオブジェクトの数をカウントします。例を見てみましょう-

注 −以下のコードは、負の数でも使用できます。

例

import java.util.*;
public class Demo{
   static void count_sort(int[] arr){
      int max_val = Arrays.stream(arr).max().getAsInt();
      int min_val = Arrays.stream(arr).min().getAsInt();
      int range = max_val - min_val + 1;
      int count[] = new int[range];
      int result[] = new int[arr.length];
      for (int i = 0; i < arr.length; i++){
         count[arr[i] - min_val]++;
      }
      for (int i = 1; i < count.length; i++){
         count[i] += count[i - 1];
      }
      for (int i = arr.length - 1; i >= 0; i--){
         result[count[arr[i] - min_val] - 1] = arr[i];
         count[arr[i] - min_val]--;
      }
      for (int i = 0; i < arr.length; i++){
         arr[i] = result[i];
      }
   }
   static void printVal(int[] arr){
      for (int i = 0; i < arr.length; i++){
         System.out.print(arr[i] + " ");
      }  
      System.out.println("");
   }
   public static void main(String[] args){
      int[] arr = {-5, 0, -3, 8, 34, 56, 89, -11, -95, -1, 10};
      System.out.println("The array contains");
      for (int i = 0; i < arr.length; i++){
         System.out.print(arr[i] + " ");
      }
      System.out.println();
      System.out.println("Implementing Counting Sort in Java results in : ");
      count_sort(arr);
      printVal(arr);
   }  
}

出力

The array contains
-5 0 -3 8 34 56 89 -11 -95 -1 10
Implementing Counting Sort in Java results in :
-95 -11 -5 -3 -1 0 8 10 34 56 89

Demoという名前のクラスには、「count_sort」関数が含まれています。ここでは、配列が繰り返され、カウント値が増分されます。

次に、このカウント配列が繰り返され、前の値が次の値に割り当てられます。配列が再度繰り返され、配列の要素が結果の配列に割り当てられ、カウント配列がデクリメントされます。次に、配列が再度繰り返され、結果の配列の要素が配列に割り当てられます。コンソールにデータを印刷する印刷機能が定義されています。 main関数は配列の要素を定義し、これらの要素のカウントソートを呼び出します。