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

계수(Counting) 정렬

---

위치를 바꿀 필요도 없이, 세기만 하면 된다.
해당 인덱스의 Counting만큼을 출력한다.
(⭐. 데이터의 크기가 한정되어 있을 때, 사용)

🕑 시간복잡도: O(N)
[ 모든 데이터를 한번씩만 접근하면 된다. ]

계수(Counting) 정렬 코드 구현

---

import java.util.*;
import java.io.*;

class Main {
  static int[] A = new int[] {1, 3, 2, 4, 3, 2, 5, 3, 1, 2, 3,
                             4, 4, 3, 5, 1, 2, 3, 5, 2, 3, 1,
                             4, 3, 5, 1, 2, 1, 1, 1};
  static int[] count = new int[6];
  public static void main(String[] args) throws IOException {
    for(int i = 1; i < 6; i++) {
      count[i] = 0;
    }

    for(int i = 0; i < 30; i++) {
      count[A[i]]++;
    }

    for(int i = 1; i < 6; i++) {
      if(count[i] != 0) {
        for(int j = 0; j < count[i]; j++) {
          System.out.print(i + " ");
        }
      }
      System.out.println();
    }
  }
}