이번에 살펴볼 Sorting algorithm은 앞에서 공부한 것들과 궤를 달리한다.
지금까지 공부한 것은 비교(comparison) 기반의 정렬이었지만
이번에는 counting 방식으로 정렬을 하는 계수 정렬(Counting sort)이다.
① basic counting sort
- 비교 행위 없이 입력값 하나씩 읽어가며 개수만 세는 것으로 정렬이 된다.
② extra memory
- 개수를 세기 위한 C(count array)가 추가로 필요하다. (= in place 알고리즘이 아니다!)
③ No stable
- 입력값의 순서가 유지되는 것을 "stable 하다"고 한다.
- 위 그림에서 3개의 "3" 입력값에 대해서 살펴보면,
. (빨간색) index 값으로 표현해보면 '3-3', '6-3', '8-3'이라고 할 수 있다. 각 '3'은 다른 '3'이다.
. 이 때, 출력값(output array)에서 '5-3', '6-3', '7-3'이 있는데,
. 입력값의 순서가 유지된 것이라고 할 수 있을까?
- Counting sort는 stable 할 수 없는 algorithm 이다.
④ Stabled(Advanced) Counting Sort
- Counting sort 를 Stable 하도록 만들 수 있다.
- Encoding ..... 기존 count array를 기반으로 누적값을 저장하는 C' array를 만들어줘야 한다.
- Decoding ..... 누적값을 갖고 있는 C' array와 입력값(A array)를 가지고 출력값(B array)를 만들어준다.
. 입력값의 제일 끝에서 부터 역으로 하나씩 처리하는 방식이다.
. 하나 더 해보면, 다음과 같다.
. 그 다음 "3" 값을 주의 깊게 봐야 한다.
왜냐하면, 처음에 했던 "3"과 이번에 해야하는 "3"은 다른 "3"이기 때문이다.
. 뭔가 신기하게 보일 수도 있긴 하지만... 그래서 뭐?
. 입력값(A array)의 3의 순서에 따라 출력값(B array)의 순서가 정해진다. → Stable 하다 !!!
⑤ Pseudo code
- 왠지 복잡해보이지만, 복잡하지 않은 코드이다.
- 변수 (메모리) 모습을 그려보면 다음과 같다.
- 여기에서 k는 입력값의 종류(개수)를 의미한다.
- 코드를 분석해보면 다음과 같다.
⑥ Running Time
- 실행 시간은 선형이다.
- 정리해보면 다음과 같다.
그 이름에 걸맞게 입력값을 하나씩 세기만 하면 되는 시간인 것이다 !!!
즉, 앞에서 살펴본 "Lower bounds for (comparison) sort" 제약에 해당하지 않는다 !!!
'Programming > Algorithm' 카테고리의 다른 글
| 알고리즘 #2 - Dynamic Programming #1 - Assembly-line scheduling #1 (0) | 2024.02.28 |
|---|---|
| 알고리즘 #1 - 정렬 문제 #8 - Radix Sort #1 (1) | 2024.02.21 |
| 알고리즘 #1 - 정렬 문제 #6 - Lower bounds #1 (0) | 2024.02.20 |
| 알고리즘 #1 - 정렬 문제 #5 - Quick Sort #1 (0) | 2024.02.06 |
| 알고리즘 #1 - 정렬 문제 #4 - Heap Sort #1 (0) | 2024.01.20 |