[ 정렬 ] 카운팅 정렬(Counting Sort) (C++)
이번 글에서는 카운팅정렬(Counting Sort) 에 대해서 다뤄보고자 한다.
사실 카운팅정렬은 값을 비교해서 정렬하는 방식이라기 보다는 값의 갯수를 세고 그 갯수에 따라서 위치를 설정해주는 방식이다.
즉, 데이터들간의 크기를 비교하거나 그런 정렬 방식이 아니다.
동작 원리는 다음과 같다.
와 같은 배열이 있다.
1. 각 데이터의 갯수를 모두 Count 해준다.
- 위의 경우 Count[3] = 2; Count[2] = 1; Count[1] = 2가 될 것이다.
2. 누적합 계산하는 방식으로 1부터 최댓값까지 계산을 해준다.
- 누적합을 계산한다는 것은 갯수를 누적하면서 더해준다는 것이다.
즉 위의 경우 Count[1] = Count[1] + Count[0] = 2;
Count[2] = Count[2] + Count[1] = 1 + 2 = 3
Count[3] = Count[3] + Count[2] = 2 + 3 = 5
3. 새로운 배열에 누적합의 갯수를 --해준 후에 저장해준다.
- 쉽게 얘기하자면 우리는 2번 과정에 의해서 Count[1] = 2 , Count[2] = 3, Count[3] = 5 라는 것을 알아냈다.
즉, 이 누적합이 의미하는 것은 들어갈 수 있는 최대 위치를 의미한다.
Count[1] = 2라고 되어있다. 즉, 정렬하게 되면 '1'이라는 값이 들어갈 수 있는 최대 위치는 두번째라는 것이다.
여기서 문제점 ! 최대 위치가 두 번째라는 것은 Index번호 몇번을 의미할까?? 바로 '1'을 의미한다.
왜냐하면 배열은 0부터 존재하기 때문이다.
따라서 우리는 값을 -- 해준 후 새로운 배열에 넣어주면 된다. 즉 위의 배열을 처음부터 탐색을 하게 되면 가장 첫 값은 '3'이기
때문에 Count[3]을 -- 해준 후, 새로운 배열에 넣어준다. 그림으로 이해해보자.
여기서 가장 첫 값이 '3'이 나왔다.
현재 Count[3] = 5 이다. Count[3]을 Index번호에 알맞게 맞춰주기 위해서 --를 해주면 Count[3] = 4.
즉, 새로운 배열의 '4'번 Index가 '3'이 된다는 것이다.
그 다음 2를 해보자. 현재 Count[2] = 3 이다.
이 3이라는 값을 Index를 맞춰주기 위해서 --를 해주면 Count[2] = 2가 된다.
즉, 새로운 배열에 '2'번 Index가 2가 된다는 것이다.
그 다음 3을 해보자. 현재 Count[3] = 4 이다.
--를 해주게 되면 Count[3] = 3. 즉, 새로운 배열에 '3'번 Index값이 3이 된다는 것이다.
나머지 1도 위와 같은 방식으로 하게 되면 결과적으로 정렬된 형태의 배열을 볼 수 있다.
# 시간복잡도
- 위의 과정을 봐서 알겠지만 비교가 필요하지도 않다. N번 탐색하면서 갯수 Count해주기, 누적합 구하기, 새로운 배열에 다시
값을 넣어주기 과정이 끝이다.
즉, 시간복잡도로 나타내면 O(N) 번 정도의 시간복잡도를 갖는다.
하지만, 데이터가 작을 때는 정말 빠르지만 데이터가 많아질수록 속도가 많이 늦어진다고 한다. 또한, 추가적으로 메모리가 요구
되는 정렬 방식이다.
그리고 본인은 마지막에 새로운 배열에 값을 넣어줄 때 원본 배열의 가장 처음(0번 Index)부터 값을 넣어줬지만 이렇게 할 경우
Unstable한 정렬이다. 반대로 가장 마지막 값 부터 넣어준다면 Stable한 정렬로 구현 가능하다.
여기서 Unstable하다, Stable하다라는 것은, 동일한 데이터에 대해서 그 순서가 바뀌지 않는 것이다.
위의 그림에서 한 부분을 따오면....
이 그림에서 '3' 2개를 봐보자. 원본 맵에서 0번 Index에 '3'이 하나 있고, 2번 Index에 '3'이 하나 있다.
하지만 정렬하고 난 후에 보면, 더 앞에 있던 즉, 0번 Index에 있던 '3'이 2번 Index에 있던 '3'보다 더 뒤로 가게 되었다.
이러한 정렬을 Unstable하다고 표현한다. 보통 우리가 주로 하는 정렬에서 이 부분까지 고려하지는 않지만 이런것도 있다 라는
것을 알고 있자 !
[ 소스코드 ]
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 | #include<iostream> #include<cstdlib> #include<ctime> #define MAX 100 using namespace std; int Arr[MAX]; int N_Arr[MAX]; int Max_Value; int Count[101]; bool Flag[101]; void Print(int A[]) { cout << "####################################################################################################################" << endl; int Cnt = 0; for (int i = 0; i < MAX; i++) { printf("%3d ", A[i]); Cnt++; if (Cnt == 20) { Cnt = 0; cout << endl; } } cout << "####################################################################################################################" << endl; cout << endl; } void Counting_Sort() { for (int i = 0; i < MAX; i++) Count[Arr[i]]++; for (int i = 1; i <= Max_Value; i++) Count[i] = Count[i] + Count[i - 1]; for (int i = 0; i < MAX; i++) { Count[Arr[i]]--; N_Arr[Count[Arr[i]]] = Arr[i]; } } int main(void) { srand((unsigned)time(NULL)); for (int i = 0; i < MAX; i++) { Arr[i] = (rand() % 150) + 1; if (Max_Value < Arr[i]) Max_Value = Arr[i]; } cout << "[ Initialize Array State ] " << endl; Print(Arr); Counting_Sort(); cout << "[ After Sort Array State ] " << endl; Print(N_Arr); return 0; } | cs |