1. 카운팅 정렬 (Counting sort) - O(n)

시간복잡도가 굉장히 빠른 counting sort에 대해 알아보자

카운팅 정렬의 메커니즘을 알아보자

짧게 얘기하자면 데이터의 값이 몇 번 나왔는지 세주는 것(counting)이다.

말보단 그림으로 확인해 보자

 

1 Step)

 

우린 이런 배열을 받았다

index	0	1	2	3	4	5	6	7	8
vlaue	4	7	0	2	7	5	1	4	3

그럼 count정렬은 각 인덱스에 들어가 있는 숫자의 개수를 정해서 

받은 숫자를 인덱스로, 들어온 횟수를 value로 지정한다.

index	0	1	2	3	4	5	6	7
value	1	1	1	1	2	1	0	2

이런 식으로 각 인덱스로 들어온 숫자를 counting 해서 넣는 것이다.

 

2.Step)

 

counting 한 배열을 누적합으로 바꿔준다.

0번째 인덱스와 1번째 인덱스

누적된 1번째 인덱스와 2번째 인덱스

                 ......

누적된 n번째 인덱스와 n+1번째 인덱스

이런 식으로 가는 것이다.

 

index0과 index1의 합은 index 1 = 1

index1과 index2의 합은 index 2 = 2

index2와 index3의 합은 index 3 = 4

이런 식으로 완성시키는 것이다.

index	0	1	2	3	4	5	6	7
value	1	2	3	4	6	7	7	9

 

3.Step ) 

마지막이다. 우선 말로 풀어보면 , counting배열의 각 값은 (시작점-1)이다.

즉, 해당 값에 대응하는 위치에 배정하면 된다

 

1. Array ) value값(4)을 counting의 인덱스로 전환

index	0	1	2	3	4	5	6	7	8
vlaue	4	7	3	2	7	5	1	4	0

2. Counting ) value에 있는 값을 모두 counting

index	0	1	2	3	4	5	6	7
value	1	1	1	1	2	1	0	2

3. 누적합 ) 누적합을 value에 표현해 준다

index	0	1	2	3	4	5	6	7
value	1	2	3	4	6	7	7	9

3. Counting ) value값을 -1 해서 result의 index 전환

index	0	1	2	3	4	5	6	7
value	0	1	2	3	5	6	6	7

4. Result ) 받은 값(value)을  result의 index값에 저장하고 3번째의 index의 값을

                 적용해 주면 된다.(만약 없다면 값이 중복되었거나 숫자가 없다는 것이다)

index	0	1	2	3	4	5	6	7	8
value	0	1	2	3	4	4	5	7	7

이런 식으로 정리가 되는 것을 볼 수 있다.

구현은 나의 깃허브에 해놓았다 시간이 된다면 보는것을 적극 추천한다

https://github.com/ProblemSolveStudy/Tae_sik/tree/master/Sorts

GitHub - ProblemSolveStudy/Tae_sik

 

---

counting Sort (카운트 정렬)

카운트 정렬은 시간복잡도가 O(n)에 속한 정령으로써 굉장히 빠른 속도의 정렬이다.

이유는 수들의 비교가 필요가 없기 때문이다.

 

하지만 이상한 점을 바로 꼽을 수 있다. 이렇게 빠른 속도의 정렬이 있음에도 불구하고

왜 퀵 정렬(O(nlogn))같은 정렬 알고리즘을 사용하는 것일까.

 

왜냐하면 단점이 너무 선명하기 때문이다. 

counting배열은 배열을 새로 선언해주어야 한다. 이는 메모리 사용량에 큰 영향을 끼치는데

우리가 다루는 배열의 개수가 20개 정도인데 수의 범위가 0~1억이라면 낭비되는 메모리량이 어마어마한 것이다.

 

그렇다면 우리가 이것을 알차게 사용하는 방법은 "수의 범위를 알고 있다"는 전제하로 코딩을 하는 것이다.

그러면 굳이 누적합을 하지 않고 반복문을 통해 인덱스를 증가시키며 array [0]부터 인덱스 값 "0"이 될 때까지 출력하면 되는 것이다

 

정리

counting Sort는 원소들을 직접 비교하는것이 아닌, 인덱스를 갖고 위치를 찾아나가는것이다.

 

 

	시간 복잡도
counting Sort(계수 정렬)	O(n)