알고리즘 공부 <6> - 카운팅 정렬 , 레딕스 정렬

이번글은 요소값을 비교하지 않아도 정렬할 수 있는 알고리즘인 카운팅 정렬 과 레딕스 정렬에  대해 공부해보도록 하겠습니다.

1. Count Sort

카운팅 정렬은 요소간 비교를 하지 않습니다. 하지만 정렬 되어지는 숫자들에 대한 가정에 의존합니다. 그 가정은 천천히 알아봅시다.

각각의 입력 요소 x 에 대해서 x 보다 같거나 작은 요소의 개수를 결정한다는 생각에서 시작 됩니다.

이를 배열 A,B,C로 나타내면 

A는 정렬하기 위한 입력값들을 넣게되는 배열

B는 정렬되어진 값들을 넣게되는 배열

C는  0부터 K까지 중 한 인덱스 i와 동일하거나 작은 값의 개수를 넣게 됩니다.

이를 그림으로 보면

a) A의 각 값의 총 개수에 대응하여 C의 인덱스에 넣어준다.  ( 0은 2개 1은 0개 ...)

b) C에 모든 요소가 들어가게 되었다면 이제 왼쪽에서 오른쪽 방향으로 값들을 누적하여 채워준다. 

c) 이제 A의 마지막 인덱스(8)부터 처음 인덱스(1)에 해당하는 값(A[i]) 과 대응하는 C의 인덱스의 값을 인덱스로 하는 B에 A의 값을 넣어 준다.

말이 어려우니 그냥 예를 보자  

A[8] = 3 

C[3] = 7

B[7] = 3 이렇게 하면된다

이후 C의 해당 인덱스의 값을 -1 해준다.  ( C[3]=7  => C[3]=6 ) 

참고로 A의 역순부터 B의 값을 넣어주는 이유는 정렬의 Stable을 지키기 위한 것이다. 값들이 들어올때 같은 값이라도 들어온 순서를 정렬 이후에도 유지시켜 주기 위한것이다.

이제 Counting Sort의 의사 코드와 빅오를 보자

빅오가 n+k 인 이유는 빅오가 k가 되는 경우가 있다 이 경우는 k>n 인 경우인데 , 즉 A의 값들이 [1, 10 ,1000 ] 이렇게 있을 경우 k=1000이 된다. 이런 경우에는 Counting Sort를 사용하지 않는 것이 좋다.

---

2. Radix Sort

앞서 Counting Sort 의 빅오를 살펴 밨는데, k의 값이 너무 커질 경우 효율이 떨어지는 것을 알 수 있었다. 이를 Radix Sort를 사용하게 되면 계산 복잡성을 낮출 수 있다.

Radix Sort는 각각의 자릿수를 기준으로 하나씩 정렬 하게 되는데 사전식 정렬 이라고 생각하면 이해하기 쉬울것 같다. 또 사전식 정렬이기 때문에 정렬을 했을 때 초기 순서가 바뀌지 않는 Stable 정렬을 이용해야 한다

이를 그림으로 보면

각 자릿수 별로 하기 때문에 Counting Sort를 사용할 경우는 k=9가 된다.

그럼 빅오를 구해보자.

Counting Sort의 빅오는 O(n+k)이고 10진수 일 경우는 k=9에 불과하다 즉 빅오는 O(n)이 된다.

그리고 자릿수가 d라면 d번 수행하게 되므로 d x O(n) 이 된다.

즉 빅오는 O(n)이 된다.

 카운팅 정렬과 레딕스 정렬에 대한 공부는 여기서 끝 

다음 공부때 봅시다.