[TIL-38/231003] 카운팅 정렬

오전에는 운동, 오후에는 집안일과 각종 잡무들을 처리하느라 많은 공부를 하지 못하였다.

백준에서 문제를 풀다가 코드가 너무 복잡해지고, 속도 또한 느리게 나오는 문제를 발견했다.

그래서 어떻게 해야할지를 고민하다가 평소에 많은 배움을 얻고 있는 Stranger-Lab님의 블로그에서 카운팅 정렬을 학습했다.

링크는 페이지 하단 참고자료란에 첨부하겠다.

 

카운팅 정렬(Counting Sort)

카운팅 정렬 사용 이유

• 시간복잡도가 O(n)으로서 엄청난 성능. 대표적인 정렬 알고리즘(퀵 정렬, 힙 정렬, 합병 정렬 등)의 평균 시간복잡도는 O(nlogn)이다.

정렬 방법

카운팅 정렬은 데이터의 값이 몇 번 나왔는지를 세는 메커니즘

 

array 배열

array 배열

 

counting 배열

array를 순회하면서 해당 값을 index로 하는 counting 배열의 값을 1 증가

counting 배열

 

counting 배열(누적합)

counting 배열의 각 값을 누적합으로 변환

counting 배열(누적합)

 

result 배열(결과값)

result 배열

counting 배열의 값은 (시작점 - 1)을 알려준다

 

진행 과정

array 배열

counting 배열(누적합)

result 배열

array의 마지막 index부터 조회

array[8]

1. array[8] = 2
2. counting[2] = 2
3. counting[2] = 2 - 1 = 1
4. result[1] = 2

counting 배열

counting 배열

result 배열

result 배열

---

array[7]

1. array[7] = 3
2. counting[3] = 4
3. counting[3] = 4 - 1 = 3
4. result[3] = 3

counting 배열

counting 배열

result 배열

result 배열

---

array[1]

1. array[1] = 3
2. counting[3] = 3
3. counting[3] = 3 - 1 = 2
4. result[2] = 3

counting 배열

counting 배열

result 배열

result 배열

---

array[0]

1. array[0] = 6
2. counting[6] = 7
3. counting[6] = 7 - 1 = 6
4. result[6] = 6

counting 배열

counting 배열

result 배열

result 배열

위와 같은 과정을 거치면 result 배열은 array 배열의 정렬된 형태로 된다.

 

장점

• 두 수를 비교하는 과정이 없어 성능이 뛰어나다.(시간복잡도 O(n))

단점

• counting 배열이라는 새로운 배열을 선언해야 한다.
• 따라서 array 안에 있는 최댓값의 범위에 따라 counting 배열의 길이가 달라진다.
  • 예) 5개의 원소를 정렬하고자 하는데 수의 범위가 0 ~ 1억이라면 메모리가 매우 낭비
• 그러므로 각기 상황에 맞게 정렬 알고리즘을 사용해야 한다.
  • 예) 퀵 정렬: 시간복잡도 평균값 O(nlogn) / 공간복잡도 O(n) (배열을 하나만 사용) → 시간과 메모리 둘 다 효율적

---

구현하기

코드는 Stranger-Lab님의 코드를 참고하였습니다.

코드

public class Main {
	public static void main(String[] args) {

		int[] array = new int[100];        // 수열의 원소 : 100개
		int[] counting = new int[100];    // 수의 범위 : 0 ~ 100
		int[] result = new int[100];      // 정렬될 배열

		// 배열에 랜덤한 값을 넣어줍니다.
		for (int i = 0; i < array.length; i++) {
			array[i] = (int)(Math.random() * 100);    // 0 ~ 100
		}

		// Counting Sort 알고리즘

		// 과정 1: 각 원소의 출현 빈도를 세어 counting 배열에 저장
		for (int i = 0; i < array.length; i++) {
			counting[array[i]]++;
		}

		// 과정 2: counting 배열을 누적합으로 변경
		for (int i = 1; i < counting.length; i++) {
			counting[i] += counting[i - 1];
		}

		// 과정 3: counting 배열을 이용하여 정렬된 결과를 result 배열에 저장
		for (int i = array.length - 1; i >= 0; i--) {
			int value = array[i];
			counting[value]--;
			result[counting[value]] = value;
		}

		// 결과 출력

		// 초기 배열
		System.out.println("초기 배열 array[]");
		for (int i = 0; i < array.length; i++) {
			if (i % 10 == 0)
				System.out.println();
			System.out.print(array[i] + "\t");
		}
		System.out.println("\n\n");

		// Counting 배열
		System.out.println("Counting 배열 counting[]");
		for (int i = 0; i < counting.length; i++) {
			if (i % 10 == 0)
				System.out.println();
			System.out.print(counting[i] + "\t");
		}
		System.out.println("\n\n");

		// 정렬된 배열
		System.out.println("정렬된 배열 result[]");
		for (int i = 0; i < result.length; i++) {
			if (i % 10 == 0)
				System.out.println();
			System.out.print(result[i] + "\t");
		}
		System.out.println();
	}
}

결과

초기 배열 array[]

66	9	98	25	10	83	14	52	65	80	
57	87	16	44	89	0	2	23	72	9	
74	71	65	55	93	11	5	23	40	80	
67	37	1	87	12	54	60	67	79	90	
52	77	86	89	12	14	42	51	37	20	
24	79	78	90	55	88	80	20	68	71	
35	42	0	50	44	77	96	85	57	78	
23	38	19	48	55	96	61	63	24	90	
79	44	55	90	42	94	39	30	48	77	
69	88	81	24	28	29	78	96	17	70

Counting 배열 counting[]

0	2	3	4	4	4	5	5	5	5	
7	8	9	11	11	13	13	14	15	15	
16	18	18	18	21	24	25	25	25	26	
27	28	28	28	28	28	29	29	31	32	
33	34	34	37	37	40	40	40	40	42	
42	43	44	46	46	47	51	51	53	53	
53	54	55	55	56	56	58	59	61	62	
63	64	66	67	67	68	68	68	71	74	
77	80	81	81	82	82	83	84	86	88	
90	94	94	94	95	96	96	99	99	100

정렬된 배열 result[]

0	0	1	2	5	9	9	10	11	12	
12	14	14	16	17	19	20	20	23	23	
23	24	24	24	25	28	29	30	35	37	
37	38	39	40	42	42	42	44	44	44	
48	48	50	51	52	52	54	55	55	55	
55	57	57	60	61	63	65	65	66	67	
67	68	69	70	71	71	72	74	77	77	
77	78	78	78	79	79	79	80	80	80	
81	83	85	86	87	87	88	88	89	89	
90	90	90	90	93	94	96	96	96	98

결과와 같이 제대로 정렬된 것을 볼 수 있다.

 

처음에는 이해가 제대로 되지 않았으나, 직접 코드를 작성하고, 중간 과정을 뜯어보면서 정리하다 보니 이제는 완전하게 이해가 되었다.

알고리즘을 집중적으로 하기보다 매일 한문제 정도씩 감을 유지하는 느낌으로 공부를 하다보니 정렬, DFS, BFS 등 필수적인 내용들을 확실하게 이해하지 못하고 있는 것을 깨달았다. 공부할 내용은 많은데 나에게 주어진 시간은 한정적이기에 아쉽다. 주어진 시간을 배분하며 최선을 다해보려 한다. 내일도 화이팅하자.

---

참고자료

https://st-lab.tistory.com/104

자바 [JAVA] - 카운팅 정렬 (Counting Sort / 계수 정렬)