Counting Sort & Radix Sort

Counting Sort & Radix Sort (기수 정렬)

- element 값을 명시적으로 비교하지 않아도 정렬할 수 있는 기법

Comparison sort = 두 개 요소 값을 반복적으로 비교하여 정렬을 수행하는 알고리즘. (Decision tree 모델 이라고도 불림)

● Counting Sort
counting sort로 1,3,2,4,3을 정렬하면
count[1] = 1;
count[2] = 1;
count[3] = 2;
count[4] = 1;
해당 개수만큼 순서대로 써주면 됨.

-> 이 방식은 stable sorting이 불가능. (stable sorting = 처음 가진 순서를 유지한 상태로 정렬을 하는 방식을 말함. 같은 값을 가졌다고 해서 순서를 마음대로 배치시키는 것이 아니라 원래의 순서를 유지하는 sorting 방식)
위와 같이 정렬하고자 하는 대상이 int type 하나만 있다면 stable sorting하는 것은 아무 의미가 없지만, pair(first, second) 형태의 데이터일때는 얘기가 달라짐.
이미 second 기준으로 정렬이 된 상태에서 first만 가지고 비교 정렬을 할 경우, unstable sorting과 stable sorting은 나오는 결과가 다를 수 있음.

counting sort로 stable sorting을 하려면? (Counting sort for stable sorting)
-> cnt 배열 자체가 index의 의미를 갖게하면 됨. 일단 cnt[x]++; 형태로 개수를 세어주고 나서 이 값을 1부터 n까지 누적시켜주면, cnt[x]-1은 정렬된 상태에서 x가 등장해야 할 마지막 인덱스를 가리키게 됨.
여기서 x값을 v[]라는 배열에 저장했다고 가정했을때, cnt[v[i]]-1은 정렬된 상태에서 v[i]가 등장해야 할 마지막 인덱스를 가리키게 됨.

● Radix Sort

입력 데이터 A의 최대값인 k가 커지면 counting sort의 효율성은 크게 떨어짐. 하지만 각각의 자릿수를 기준으로 정렬을 하게 되면 계산 복잡성을 낮출 수 있음. 10진법으로 표기된 숫자를 정렬한다면 k는 9가 됨. 
주의할 것은 각 자리수를 기준으로 정렬할 때 정렬 대상 숫자들의 위치가 뒤바뀌지 않는 stable sort 알고리즘을 적용해야 한다는 것. 특정 자릿수를 놓고 정렬할 때 그 위치가 바뀌게 되면 해당 숫자가 아예 다른 숫자가 되어버리기 때문. unstable sort를 적용하면 14, 21 ==> 11, 24 같은 엉뚱한 결과가 나올 수 있음.

radix sort를 linked list로 구현할 수도 있음. 10진수 첫번째 자리를 기준으로 정렬한 뒤, 두번째 자리를 기준으로 정렬. 정렬 순서를 유지하기 위해 linked list 삽입시 head에 넣지않고 tail에 삽입하는 것이 특징. 

낮은 자리수부터 비교하여 정렬해가는 알고리즘. 비교 연산을 하지 않으며 정렬 속도가 빠르지만 데이터 전체 크기에 기수 테이블의 크기만한 메모리가 더 필요함.

ex) 세자리 수가 여러개 있을 때
① 먼저 일의 자리수 비교하고 정렬
② 십의 자리수 비교하고 정렬 (일의 자리수 비교하여 정렬한 순서 그대로 들어옴, 십의 자리수가 2인경우, 일의 자리수에서 정렬했던 720, ... , 329, 해당 순서 그대로 들어옴)
③ 백의 자리수 비교하고 정렬 (②번과 마찬가지로 십의 자리수까지 비교하여 정렬한 순서 그대로 들어옴)

Radix sort의 계산 복잡성을 따져볼 때, counting sort가 O(n + k)이고 10진수를 예로 들 때 k는 9에 불과하므로, 특정 하나의 자릿수를 기준으로 counting sort하는데 드는 비용은 O(n)이 될 것. 그런데 전체 자릿수가 d라면 이를 d번 수행해야 함. 따라서 전체적인 복잡성은 d * O(n)이 됨. 1조(=10^12)같은 큰 숫자가 끼어 있어도 d는 12에 불과하기 때문에 선형시간에 가깝게 정렬을 수행할 수 있음.