Counting Sort

 

❐ Description

---

[LeetCode#274] HIndex를 풀면서 Counting Sort를 알게 됐다. 이를 직접 구현해보자!

 

 

 

 

 

❐ 특징

---

• 시간 복잡도
  • 최선, 평균, 최악 모구 O(n+k)
  • n : 정렬할 데이터의 개수
  • k : 데이터 값의 범위
• 비교 기반이 아님
  • 데이터를 비교하지 않고, 데이터의 출현 횟수만 이용하여 정렬한다.
• 안정정렬
  • 데이터의 순서를 유지하며 정렬한다.
• 한계점
  • 데이터 범위가 크면 비효율적이다.
  • 정수 또는 정수로 변환 가능한 데이터에만 사용할 수 있다.
    • 부동소수점이나 복잡한 객체에는 적합하지 않다.

 

 

 

 

 

❐ 순서대로 구현해보기

---

Step1. 주어진 배열의 요소 중 최댓값 찾기

int maxElement = Arrays.stream(nums).max().getAsInt();

 

 

Step2. 길이가 `최대값 + 1`인 countArray 초기화 하기

int[] countArray = new int[maxElement + 1];

 

 

Step3. `countArray[]`에 입력 배열의 각 고유 요소의 개수를 각각의 인덱스에 저장

for (int num : nums) {
    countArray[num]++;
}

 

 

Step4. `countArray[]` 요소의 누적 합 계산

for (int i = 1; i < countArray.length; i++) {
    countArray[i] = countArray[i - 1] + countArray[i];
}

 

 

Step5. 입력 배열의 끝부터 순회하면 outputArray 채우기.

출처 : https://www.geeksforgeeks.org/counting-sort/

int[] outputArray = new int[nums.length];

for (int i = nums.length - 1; i >= 0; i--) {
    int inputNum = nums[i];

    int count = countArray[inputNum];
    countArray[inputNum]--;

    outputArray[count - 1] = inputNum;
}

 

 

 

 

 

❐ 전체 코드

---

public class CountingArray {

    public static void main(String[] args) {

        int[] nums = {2, 5, 3, 0, 2, 3, 0, 3};

        // Step 1
        int maxElement = Arrays.stream(nums).max().getAsInt();

        // Step 2
        int[] countArray = new int[maxElement + 1];

        // Step 3
        for (int num : nums) {
            countArray[num]++;
        }

        // Step 4
        for (int i = 1; i < countArray.length; i++) {
            countArray[i] = countArray[i - 1] + countArray[i];
        }

        // Step 5
        int[] outputArray = new int[nums.length];

        for (int i = nums.length - 1; i >= 0; i--) {
            int inputNum = nums[i];

            int count = countArray[inputNum];
            countArray[inputNum]--;

            outputArray[count - 1] = inputNum;
        }

        // Step 6
        String result = Arrays.stream(outputArray).boxed().toList().toString();
        System.out.println(result);
    }

}

 

 

 

 

 

---