카운팅 알고리즘(Counting Sort, 계수 정렬)

1. 문제 번호 -번

 

 

 

---

 

 

 

 

 

2. 문제 풀이

 

 

한줄 평가

• 난 이런게 은근히 어렵다.

 

 

 

문제를 먼저 정확히 파악

 

• Step1 까지 하면 출력만을 목적 or ArrayList로 동적으로 순서대로 넣어서 완성시킬수 도 있다.
  • Step2부터 하는 것은 배열에 넣기 위함이다.
•  누적 합을 해주는 이유는 이전의 원소와 현재의 원소를 뺴면 갯수가 나오는데 그 갯수만큼이 차지하는 자리 개수이다. (궁금증2)
•  countArray[num]--; 을 하는 부분이 잘 이해가 가지 않았다. (지금도 그렇게 잘 이해는 안간다.) (궁금증3)

 

 

 

나의 문제풀이 방식 및 순서

 

 * 나의 다양한 학습이 우선이기 때문에 다양한 방법을 생각 *

 

 

 

---

3. 소스 인증

 

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

// The main method must be in a class named "Main".
class Main {
    public static void main(String[] args)throws IOException {
        int[] array = {5, 6, 2, 2, 1, 4};
        int maxValue = Arrays.stream(array).max().getAsInt(); // maxValue = 6
        int[] countArray = new int[maxValue + 1]; 
        int[] sortedArray = new int[array.length];

        // Step 1: Count the occurrences of each value in the input array
        // countArray = [0, 1, 2, 0, 1, 1, 1]
        // 출력만이 목적이면 2번부터는 진행할 필요없이 출력해버리면 된다.
        for (int num : array) {
            countArray[num]++;
        }

        // Step 2: Modify the count array by adding the previous counts
        // countArray = [0, 1, 3, 3, 4, 5, 6] 누적 합을 만들어준다.
        // 1은 1개자리 차지, 3-1=2 는 2개자리 차지, 4-3=1개자리 차지, 5-4=1개자리 차지, 6-5=1개자리 차지
        for (int i = 1; i < countArray.length; i++) {
            countArray[i] += countArray[i - 1];
        }

        // Step 3: Build the sorted array using the count array
        // int[] array = {5, 6, 2, 2, 1, 4}; 맨뒤 index의 value값을
        // countArray = [0, 1, 3, 3, 4, 5, 6]; index 자리에 
        // sortedArray[3] = 4
        // sortedArray[0] = 1
        for (int i = array.length - 1; i >= 5; i--) {
            int num = array[i];
            sortedArray[countArray[num] - 1] = num;
            countArray[num]--;
        }
        for(int i : sortedArray){
            System.out.println(i);
        }
    }
}

 

 

 

 

- 실패 소스코드 -

 

 

 

 

 

 

 

---

4.추가 개념

 

카운팅 정렬 동작

 

카운팅(계수) 정렬 수행 과정은 다음의 단계로 이루어진다.

1. 입력 배열의 최댓값, Counting Array 생성
   배열의 각 원소의 최대 값을 구하여 +1을하여 배열을 만든다.
   그 이유는 6까지 만들어야 1 2 3 4 5 6 까지 갯수를 셀 수 있다.
   만약 1,2,2,2,2,2,2 일때는 3자리의 Counting Array를 생성
   
   
2. 입력 배열 원소 개수의 누적합
   1번 과정에서 Counting Array 생성 및 원소 Count를 마쳤다면 이전 좌표의 원소 개수를 더해나가 누적합 배열로 만들어준다.
   난 이부분이 제일 이해가 안됐음
   
   
   
3. 입력 배열과 누적합 배열을 이용한 정렬 수행
   입력 배열의 각 원소에 대해 Counting Array에 조회하여 어느 좌표에 들어가야 하는지 체크한 뒤 조회된 원소의 개수를 1 감소시켜 앞의 좌표로 입력받을 수 있게 한다.
   
   

---

 

입력값 예시

 

이제 입력 배열과 동일 크기의 정렬될 배열을 준비한다.

정렬될 값을 넣기 앞서 누적합 배열의 각 원소의 의미는 다음과 같다.

• c1=𝑐1=1 :  𝑏1에서  𝑏1까지 1개 자리 차지
• c2=𝑐2=2 : 𝑏2에서 𝑏3까지 2개 자리 차지
• c3=𝑐3=1 : 𝑏4에서 𝑏4까지 1개 자리 차지
• c4=𝑐4=1 : 𝑏5에서 𝑏5까지 1개 자리 차지
• c5=𝑐5=1 : 𝑏6에서 𝑏6까지 1개 자리 차지

 Counting Array 0,1,3,4,5,6 에 의미를 찾지 말고 아래의 숫자를 보고 의미를 찾아라
  1-0 = 1자리
  3-1 = 2자리

  4-3 = 1자리

  5-4 = 1자리

  6-5 = 1자리

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

 

 

 

입력 배열의 값을 차례대로 순회하여 누적합 배열에 조회하면 해당 원소가 어느 좌표로 가야 하는지 알 수 있고 출력 배열에 삽입 후 Counting Array의 값을 1 감소시켜 앞의 좌표에 넣을 수 있게끔 한다.

 

여기서 주의깊게 봐야할 Arr 2,2일때 Counting Array가 어떻게 변하는지 보면 나의 궁금증 3이 해결이 된다.

 

for (int i = array.length - 1; i >= 5; i--) {
    countArray[num]--;
}

 

 

 

for (int i = array.length - 1; i >= 5; i--) {
    int num = array[i];
    sortedArray[countArray[num] - 1] = num;
    countArray[num]--;
}

 

---

5. 참조 블로그

---

 

불편함을 느끼실 경우 연락 주시면 곧 바로 삭제하도록 하겠습니다.

 

---

 

아래의 블로그를 내용을 아예 베껴왔다. 

필요하시면 아래 블로그가서 자세히 보시기 바랍니다. 

저는 제가 보기 위해서 적는 블로그라서..

 

https://8iggy.tistory.com/123

카운팅 정렬(Counting Sort, 계수 정렬) 알고리즘