[JAVA] 카운팅 정렬 step3 완벽 이해

내가 이해하기 어려웠던 카운팅 정렬...

하나씩 따라쳐보며 이해하기 !

 

---

1. 서론

---

int[] arr = {5, 2, 4, 1, 2, 3, 3};

해당 배열을 오름차순으로 재배치하기 위해서 [버블 정렬, 선택정렬] 등 많이 있겠지만 이는 O(n^2)의 시간복잡도, 빅오를 가져서 효율적인 정렬 방법과는 뒤떨어진다.

 

하지만 카운팅 정렬은 항목들의 순서를 결정하기 위해 집합에 각 항목이 몇 개씩 있는지 세는 작업을 하여, 선형시간(O(n+k))에 정렬하는 효율적인 알고리즘이다.  n은 배열의 길이, k는 정수의 최대값이다.

 

 

 

---

2. 카운팅 정렬

---

 

import java.util.Arrays;

public class 카운팅정렬 {

	public static void main(String[] args) {
		int[] arr = {5, 2, 4, 1, 2, 3, 3};
		
		//step1. 수 카운팅 - 1이 몇 번나오니? 2가 몇 번 나오니? 
		int[] count=new int[6]; //arr의 가장 큰 수가 5이기 때문에 
		
		for(int i=0;i<arr.length;i++) {
			count[arr[i]]++;
		}
		System.out.println(Arrays.toString(count));
		
		//step2. 누적합 
		for(int i=1;i<count.length;i++) {
			count[i]+=count[i-1];
		}
		
		System.out.println(Arrays.toString(count));
		
		//step3. 카운팅 정렬 - 오름차순 
		//arr 뒤부터 돌면서 arr 특정수에 해당하는 count index로 접근
		//ex arr[7]=3 -> count[3]=5; -> nums[4]부터 채워줌 -> count[3]--
		int[] nums = new int[7];
		for(int i=arr.length-1;i>=0;i--) {
			//arr[7]=3 -> count[3]=5; -> nums[4]부터 arr[7]의 값 3을 채워줌
			nums[count[arr[i]]-1]=arr[i];
			count[arr[i]]--;//count[3]=5; -> 4
		}
		System.out.println(Arrays.toString(nums));
	}

}

[코드 결과]

 

 

[설명]

 

step1. 수 카운팅

1이 몇 번나오니? 2가 몇 번 나오니? 를 count 배열에 체크한다. 이 때 arr배열의 값 중 가장 최대 값이 뭔지 파악해야 count 배열의 크기를 결정할 수 있다.

 

그럼 위의 결과는 [0, 1, 2, 2, 1, 1]이 나온다.

(0 - 0개 / 1 - 1개 / 2 - 2개 / 3 - 2개 / 4 - 1개 / 5- 1개)

 

step2. 누적합 

수 카운팅을 해준 count 배열을 이용해 누적합 배열을 새로 만든다.

[0, 1, 3, 5, 6, 7]이 나온다.

 

count = {0, 1, 2, 2, 1, 1}를 통해 다시보자면, 

0 - 0

1 - 0+1

3 - 0+1+2

5 - 0+1+2+2

6 - 0+1+2+2+1

7 - 0+1+2+2+1+1

위 과정을 통해 count={0, 1, 3, 5, 6, 7}로 count 배열이 재탄생 된 것이다.

 

count={0, 1, 3, 5, 6, 7} 이들의 의미는 아래와 같다.

 

count[0] - 0은 하나도 없다.

count[1] - 1은 1-1 = 0번 인덱스까지 차지한다.

count[2] - 2는 3-1 = 2번 인덱스까지 차지한다.

count[3] - 3은 5-1 = 4번 인덱스까지 차지한다.

count[4] - 4는 6-1 = 5번 인덱스까지 차지한다.

count[5] - 5는 7-1 = 6번 인덱스까지 차지한다.

 

 

 

step3. 카운팅 정렬 - 오름차순 

int[] arr = {5, 2, 4, 1, 2, 3, 3};
int[] nums = new int[7]; //카운팅 정렬 결과를 저장할 배열
//현재 count배열 현황 -> count={0, 1, 3, 5, 6, 7}

 

arr 맨 뒤 인덱스부터 돌면서 arr 특정수에 해당하는 count index로 접근한다.

ex) arr[7]=3 -> count[3]=5; -> 5-1인 nums[4]부터 채워줌 -> count[3]--

 

count[3]--를 해주는 이유는 또 arr의 특정 인덱스 값이 3인 경우 이전에 3을 채워준 nums 인덱스의 앞에 3을 채워주기 위함이다.

결과는[1, 2, 2, 3, 3, 4, 5]로 정렬되는 것을 볼 수 있다.