계수정렬은 기수정렬처럼 원소들끼리의 크기비교가 아닌 어느 절대적인 값들과 비교를 통해서 상당히 빠른속도로 정렬을 할 수 있다. 어떠한 절대적인 값이 있을지 생각해보면, 우리가 정렬을 프로그래밍 할때, 대부분이 배열을 사용해서 정렬되지 않은 원소들을 넣은 상태에서 진행을 했을텐데, 이때의 배열 인덱스 값을 이용한 방식이다.
계수정렬의 방식은 정렬되지 않는 원소들을 새로운 배열에다가 저장을 할 것인데, 이 새로운 배열의 크기는 전체원소들 중 가장 큰 원소를 배열의 크기로 놓으며, 배열 인덱스에 해당 원소들이 몇 개 있는지 넣어주면 된다. 예를들어 " A = { 2, 5, 4, 2, 4, 5 } "라는 정렬되지 않은 원소들이 있다면 가장 큰 원소 5만큼 새로운 배열 " C[5]; "를 만든다. 그런다음 배열 A의 전체 값들을 새로 만든 배열 C[5]에 다음과 같이 넣어주면 된다.
" 배열 인덱스에 해당하는 각 숫자들이 몇 개씩 있는지 세어주면 된다 "
ex) 2, 5, 4, 2, 4, 5의 값들이 있을경우,
C[0] = 0, C[1] = 0, C[2] = 2, C[3] = 0
C[4] = 2, C[5] = 2
C[4] = 2, C[5] = 2
그리고 정렬 될 값들을 저장할 " B[6] " 라는 배열에 차례로 저장하면 된다. 총 3개의 메모리가 필요하며, 중복되는 값들을 정렬 할 때는 편리하겠지만 만약에 원소들이 1, 3, 5000, 1이런식으로 존재한다면, 가장 큰 원소 5000을 C[5000]과 같이 만들어야 하므로 매우 비효율적으로 정렬 될 수도 있다. 이것은 "우리가 정렬을 하기 전 먼저 원소들의 크기가 어떠한지 고려해야 한다" 라고 말하는 의미다.
위의 내용을 간략히 정리하면,
1. A배열 전체에서 가장 큰 원소만큼 배열 C를 만들기
2. A배열 원소 하나씩 C배열의 인덱스에 해당하는 것끼리 넣어주기
3. 각 원소들이 저장된 C배열을 B[N]에 하나씩 정렬시키기
ex) 계수정렬 과정
---------------------------------------------------------------------------
 |
| 계수정렬 과정 ( 1 ) |
 |
| 계수정렬 과정 ( 2 ) |
 |
| 계수정렬 과정 ( 3 ) |
 |
| 계수정렬 과정 ( 4 ) |
 |
| 계수정렬 과정 ( 5 ) |
 |
| 계수정렬 과정 ( 6 ) |
: 정렬이 완료 되었다.
위에 설명한 배열C 또한 그림에 표현하면 더 좋아겠지만, C는 알고리즘을 구현 시 사용이 되며, 위에서 설명한 계수정렬을 알고리즘 위주로 쓰다보니, 계수정렬을 조금 흐릿하게 설명하여 그림으로 보다 명확한 계수정렬을 표현하고 싶었다.
---------------------------------------------------------------------------
계수정렬의 수행시간은 다음 2가지를 고려하면 된다.
(1) 전체 A[N]의 원소들을 C[ 전체 N개중 가장 큰 원소 ]에 해당하는 원소들의 갯수만큼 정의
: (1)의 수행시간은 가장 큰 원소만큼의 수행시간이 필요하다. ( 수행시간 C : 상수 )
(2) B[0], B[1] ... B[N]에 차례로 옮겨 정렬시키면 된다.
: (2)의 수행시간은 전체 갯수인 N만큼의 수행시간이 걸린다. C[A[i]]에 해당하는 값들을 B[N]만큼 차례로 옮기면 되므로 ( 수행시간 N : 전체원소의 갯수 )
(1), (2)를 정리하면 계수정렬의 수행시간은 Theta(N)의 특징을 보인다. 그리고 위에서도 말했듯이 메모리를 3개나 준비해야 하는것과 비교적 큰 숫자가 등장하면 C의 메모리가 꽤 커진다는 문제가 있지만, 장점 측면에서, 예를 들어 5이하의 자연수 100개가 모여있다고 가정했을 경우, 어느 정렬방식과는 비교할 수 없는 빠른 수행을 자랑한다.
계수정렬의 알고리즘
▶ 실행결과
댓글 없음:
댓글 쓰기