카운팅 정렬(+ 선택 정렬)

이 수는 몇 개 있으니까 여기 놓고 저 수는 몇 개 있으니까 저기 놓고… 더보기

---

많고 많은 정렬 알고리즘 중 정렬할 수의 범위가 한정적일 때 쓸 수 있는 카운팅 정렬을 공부해 보자. 선택 정렬은 덤이다.

1. 정렬 알고리즘

위키백과에 따르면 ‘원소들을 번호순이나 사전 순서와 같이 일정한 순서대로 열거하는 알고리즘’이라고 한다. 선택 정렬, 버블 정렬, 퀵 정렬 등등 종류가 꽤 많다. 데이터를 의미있게 만드는 데 유용하게 쓴다.

정렬 알고리즘은 출력 형식이 정해져 있다.

• 비내림차순일 것 : 어떤 배열 A의 원소 a_i와 a_j에 대해 i < j일 때, a_i ≤ a_j이어야만 한다.
• 입력을 재배열하여 만든 순열일 것

1-1. 시간 복잡도

정의 : 문제를 해결하는데 걸리는 시간과 입력의 함수 관계
크기가 n인 입력에 대하여 문제 해결에 걸리는 시간을 식으로 나타내는 것으로 주로 빅-오 표기법을 사용하는데, 이 표기법은 계수와 낮은 차수의 항을 제외시킨다. 예를 들어 크기가 n인 입력에 대해 어떤 알고리즘에 필요한 시간이 최대 an² + bn(a ≠ 0)이라고 한다면, 이 알고리즘의 시간 복잡도는 O(n²)이라고 표기하는 것이다. (출처 위키백과)

2. 카운팅 정렬

요약 : 주어진 수열에서 각각의 숫자가 종류별로 몇 개씩 등장하는지 센 다음, 그 개수에 맞추어 원소를 새로 나열한다. 등장하는 수의 범위가 제한적일 때 사용할 수 있다.

여기 0부터 9까지의 숫자를 대충 흩뿌린 배열이 하나 있다. 순서도 맞지 않고, 중복도 있다. 없는 숫자도 있을 수 있다. 총 원소 개수는 15개이다.

ar = [ 3, 4, 2, 6, 8, 2, 9, 0, 4, 8, 7, 5, 2, 4, 0 ]

이제 0부터 9까지 원소가 총 10개인 배열을 만들어 위의 배열에 나오는 원소들의 개수를 세자. 예를 들어 3은 1개, 8은 2개 이런 식으로 세는 것이다. 셈한 수의 개수는 아까 만든 크기가 10인 배열에 저장한다. 다 세면 다음과 같다.

cn = [ 2, 0, 3, 1, 3, 1, 1, 1, 2, 1 ]

다음으로 이 개수들을 누적하여 합한다. 0번 원소는 그대로 두고, 1번 원소는 (0번 + 1번), 2번 원소는 (0번 + 1번 + 2번) 이런 식으로 더하면 된다. 이렇게 누적된 개수는 각 숫자가 마지막으로 나열될 위치의 인덱스 + 1과 같다. 다시 말해 각 숫자가 마지막으로 몇 번째 자리에 나와야 하는지를 의미하게 된다.

cn = [ 2, 2, 5, 6, 9, 10, 11, 12, 14, 15 ]

이제 이 수들에 맞춰 정렬하지 않은 배열을 새 배열에 넣으면 된다. 배열의 인덱스보다 1 크게 저장되어 있으니 먼저 1을 빼고 나온 수의 인덱스에 맞추어 넣으면 된다. 수를 넣기 전에 매번 1을 빼기 때문에 남은 누적 인덱스의 업데이트도 겸하는 셈이다. 정렬된 배열은 아래와 같다.

sorted_ar = [ 0, 0, 2, 2, 2, 3, 4, 4, 4, 5, 6, 7, 8, 8, 9 ]

내가 공부를 위해 찾아봤던 블로그에서 좋은 자료를 인용해 두어서 같이 올린다. 카운팅 정렬의 과정을 애니메이션으로 만들었다.
링크 : 참고한 블로그, 카운팅 정렬 애니메이션

2-1. 굳이 원소 개수를 누적해서 자리를 계산하는 이유

내가 생각해낸 의문은 아니고(궁금해하기도 전에), 참고했던 블로그에 설명되어 있던 것이다. 아까 cn 배열에 원소 개수를 세었을 때, 각각의 원소 개수만큼 바로 반복문에 넣어 출력해도 될 것 같은데 왜 그러지 않고 굳이 누적하여 새 배열에 넣었을까?

아까와 같은 예시에서는 원소 개수만으로 반복문을 넣어 출력하는 방법이 통할지도 모른다. 빠진 숫자가 거의 없고 전체적으로 개수가 고르게 퍼져 있으니 카운팅 정렬을 하나, 원소 개수대로 출력하나 큰 차이는 없을 것이다. 그러나 만약 1부터 100까지의 숫자가 들어갈 수 있고, 포함된 원소는 아래와 같은 배열을 정렬한다면 어떨까?

ar2 = [ 1, 100, 95, 96, 95, 99, 2, 100, 97, 98 ]

개수를 세고 나면 개수 배열에는 값이 0인 원소가 대부분일 것이다. 이 배열을 원소의 값만큼, 즉 각 숫자의 개수만큼 매번 반복문을 넣어 출력하도록 한다면 개수가 0개인 3부터 94까지는 무의미한 반복문을 실행하게 될 것이다. 프로그램의 입장에서는 배열의 값이 0이라는 것만으로는 반복문을 들어가야 하는지, 그냥 지나쳐도 되는지 알 수 없다. 우선 반복문의 시작인 for문이 써있는 줄을 들어가 보고, 반복에 사용하는 변수가 반복 조건에 맞지 않는 것을 확인한 다음에 이후 실행할 코드로 넘어간다. 그러니 이 예시에서는 92번의 무의미한 반복문 방문이 생긴다.

반면 인덱스를 누적하여 계산하고 그에 따라 새 배열에 원소를 삽입하면, 개수 배열의 어느 원소를 방문할지는 정렬해야 할 원래 배열의 원소에 따라 정해지기 때문에 개수 배열의 3번부터 94번 원소까지는 아예 건드릴 일이 없다. 이로써 92번의 무의미한 실행을 방지했다.

(22.02.03 수정) 일단은 시간적 효율을 생각해서 저렇게 정렬하면 안 되는 것처럼 설명하긴 했지만, 시간을 좀 더 쓰는 대신 메모리가 아주 부족한 상황에서 정렬을 해야 한다면 저런 방법이 해결책이 될 수도 있다. 너무 정석에 얽매이지 말자..

3. 선택 정렬

요약 : 전체 배열에서 가장 작은 것을 골라 맨 앞에 앉히고 남은 배열을 다시 비교한다. 비교할 배열이 없을 때까지 반복한다.

여기 아까 썼던 배열이 있다.

ar = [ 3, 4, 2, 6, 8, 2, 9, 0, 4, 8, 7, 5, 2, 4, 0 ]

이제 마치 맨땅에 헤딩하듯이 아래와 같은 과정을 수행할 것이다.

1. 첫 번째 원소를 잡고 두 번째부터 끝까지 일일이 비교해가며 전체 배열에서 가장 작은 수를 찾는다. 검사가 끝나면 가장 작은 수와 첫 번째 원소의 자리를 바꾼다.
2. 두 번째 원소를 잡고 세 번째부터 끝까지 일일이 비교해가며 전체 배열에서 가장 작은 수를 찾는다. 검사가 끝나면 가장 작은 수와 두 번째 원소의 자리를 바꾼다.
3. 세 번째 원소를 잡고 네 번째부터 끝까지 일일이 비교해가며 전체 배열에서 가장 작은 수를 찾는다. 검사가 끝나면 가장 작은 수와 세 번째 원소의 자리를 바꾼다.
4. (중략) 14번째 원소를 잡고 15번째부터 끝까지 비교한다만 15번째가 끝이니 둘 중 작은 수를 찾는다. 그리고 작은 수와 14번째 원소의 자리를 바꾼다. 정렬이 끝났다.

카운팅 정렬에 비하면 비효율적이지만 아무튼 정렬은 되는 방법이다. 선택 정렬의 시간 복잡도는 O(n²)이다. 위의 예시대로 코드를 작성해, 서로 다른 두 원소를 비교하는 선택문 실행 횟수만 세어보면 105번이 나온다. 직접 세어보긴 했지만 이 횟수를 구하는 공식도 인터넷에 검색하면 금방 알 수 있다. 전체 원소 개수를 n이라고 할 때, n(n - 1)/2이다.

4. 덤

내가 왠지 할 수 있을 것만 같은 자신감이 들어서 첫 번째 예시의 배열을 선택 정렬로 정렬하는 코드와 같은 것을 카운팅 정렬로 정렬하는 코드를 모두 써보았다. 그리고 선택 정렬은 서로 다른 두 원소를 비교한 횟수를, 카운팅 정렬은 반복문의 총 실행 횟수를 세었다. 실행 결과 선택 정렬은 105번이 나왔고, 카운팅 정렬은 39번이 나왔다. 입력되는 값의 범위를 알아야 하고, 그 범위가 지나치게 크지 않아야 한다는 제약이 있지만 내가 다음에 풀게 될 문제를 해결하기엔 충분한 알고리즘이다. 백준 10989 수 정렬하기 3 문제다. 혹시 될까 해서 sort 함수(C++)를 써봤는데 역시나 틀렸었다. 소스 코드 링크를 올려둘 테니 직접 실행해보고 싶다면 복사해서 붙여넣어보자.

[C++ 소스 코드]
(1) 선택 정렬
(2) 카운팅 정렬

[파이썬 소스 코드]
(1) 선택 정렬
(2) 카운팅 정렬