[알고리즘] Counting Sort (계수 정렬)

🔍 Learn

Counting Sort (계수 정렬)

Counting Sort 알고리즘은 추가적인 배열을 이용하여, 두 수를 비교하는 과정 없이 정렬하는 알고리즘으로, 시간복잡도는 O(n)이다.

일반적으로 빠르다는 정렬 알고리즘의 평균 시간복잡도는 O(nlogn)이다. 이에 비하면 Counting Sort는 굉장히 빠른 시간이지만, 메모리 낭비와 정수로 표현되는 자료에 제한된다는 등의 단점으로, 보통은 O(nlogn)의 정렬 알고리즘을 이용한다. Counting Sort는 정렬할 데이터의 크기가 비교적 작을 때 효율적이다.

📌 알고리즘

1. array를 순회하며, 각 값이 나올 때마다 해당 값을 index로 하는 count 배열의 값을 1 증가시킨다.

   ex. if arr[3] == 1 -> count[1] += 1;
   
   

   (이미지 클릭 시 출처 페이지로 이동)

2. count 배열의 각 값을 누적 합으로 바꾼다.

   ex. count = {2, 1, 2, 2, 3} -> count = {2, 3, 5, 7, 10}
   

3. array를 순회하며, 각 값을 인덱스로 하는 count 배열의 값에 -1을 하고, 수정된 count 배열의 값을 인덱스로 하는 result 배열 자리에 array 배열의 값을 집어 넣는다.

   ex. if arr[8] == 4 -> count[4]-- -> count[4] = 9 -> result[9] = 4 (arr[8])
   

4. result 배열은 정렬된 array배열과 같다.

---

구현

💻 Code

public class CountingSort {
  public static void main(String[] args) {
      int[] arr = new int[100];
      int[] count = new int[21];
      int[] result = new int[100];

      /* Step 1 */
      for (int i = 0; i < arr.length; i++){
          // arr 배열에 임의의 값을 지정함과 동시에
          arr[i] = (int) (Math.random() * 20 + 1);
          // arr 배열의 값을 index 로 하는 count 배열 값 +1
          count[arr[i]] += 1;
      }

      /* Step 2 */
      for(int i=1; i<count.length; i++)
          count[i] += count[i-1];

      /* Step 3 */
      for(int i=0; i<arr.length; i++){
          int temp = arr[i];
          count[temp]--;
          result[count[temp]] = arr[i];
      }


      /* 배열 비교 출력 */
      System.out.print("array :");
      for(int i=0; i<arr.length; i++){
          if(i%10 == 0)
              System.out.println();
          System.out.print(arr[i] + "\t\t");
      }

      System.out.println();
      System.out.println();

      System.out.print("count :");
      for(int i=0; i<count.length; i++){
          if(i%10 == 0)
              System.out.println();
          System.out.print(count[i] + "\t\t");
      }

      System.out.println();
      System.out.println();

      System.out.print("result :");
      for(int i=0; i<result.length; i++){
          if(i%10 == 0)
              System.out.println();
          System.out.print(result[i] + "\t\t");
      }
  }
}

출력