Radix Sort

오랜만에 나는 야호다.

오늘은 라딕스 소트라는걸 배워보자.

본인은 매우 애용한다.

Counting Sort

Radix Sort를 배우기 전에 우리는 Counting Sort에 대해 알아보아야 한다.

만약 다음과 같은 문제가 주어졌다고 하자.

1000만 개의 숫자가 주어진다. 각 숫자는 0 또는 1이다. 이를 정렬하라.

비교기반 정렬을 때리면, $$O(nlogn)$$으로 매우 오랜시간이 걸린다. 하지만 우리는 다음과 같은 관찰을 할 수 있다.

정렬된 배열은 항상 0, 0, 0,0, ... , 0, 1, 1, 1, ... , 1, 1꼴이다.

그렇다. 따라서 우리는 0과 1의 개수를 세준 다음 그 개수만큼의 0과 1을 놓으면 되는 것이고, 이 때의 시간복잡도는 당연히 $$O(n)$$이다.

이는 숫자가 여러개일 때도 동일하게 작동한다. 즉, 다음과 같은 문제도 비슷하게 $$O(n)$$에 구현할 수 있다.

1000만 개의 숫자가 주어진다. 각 숫자는 0이상 100 미만이다. 이를 정렬하라.

당연히 각각의 숫자가 몇개인지 확인해야하므로, 가능한 숫자의 범위를 $$k$$개라 하면 이 Counting Sort의 시간복잡도는 $$O(n+k)$$가 된다.

잠깐 Stable Sort의 정의에 대해 알아보자.

Stable Sort란 같은 값을 가진 자료들이 정렬될 때 그 순서를 유지하는 정렬을 의미한다.

즉, 위에서 말한 Counting Sort는 값을 새로 만들어내고 있으며, 이 값들은 원래의 값에서 유래한 값이 아니니까, Stable Sort가 아니다.

하지만 우리는 다음과 같은 방법으로 Counting Sort를 Stable하게 만들수 있다.

각 숫자별로 개수를 세준다.
개수를 센 배열의 prefix sum을 구해준다.
예를 들어, 0이 2개, 1이 3개, 2가4개라고 하면 prefix sum은 2, 5, 9가 된다.
정렬결과를 담을 배열을 만든다.
원배열을 역순으로 탐색하면서 해당하는 prefix sum의 값을 찾아가자.
이 값에서1을 뺀것이 인덱스가 된다.
4번에서 구한 인덱스에 원배열의 값을 대입.
4번으로 돌아가 배열을 전부 탐색할 때까지 반복

자 이렇게 하면 똑같은 숫자의 경우 index가 뒤쪽에 있는 녀석부터 뒤에서 순서대로 넣기 때문에 항상 stable하게 정렬이 된다.

자 드디어 Radix Sort에 대해 알아보자. Radix Sort는 Counting Sort가 Stable하기 때문에 가능한 정렬이다.

1000만 개의 숫자가 주어진다. 각 숫자는 0이상 100 미만이다. 이를 정렬하라.

이문제를 다시 생각해보자.

Radix Sort는 다음과 같은 방법으로 정렬되는 알고리즘이다.

각 과정이 Stable하기 때문에 저 과정을 마치고나면, 정렬된 배열을 얻을 수 있게 된다.

자리수가 $$d$$개라면 Radix Sort의 시간복잡도는 $$O(d(n+k))$$이다.

참 쉽죠?

Note) integer 범위의 수에 대해서 d=2, k=1<<16을 종종 사용한다. 숫자의 범위가 커도 적당히 진법을 변경하여, $$O(n)$$정도의 시간복잡도로 구현이 가능하다.