radix sort란?
한국어로는 기수정렬로 bucket sort의 일종으로, 기수별로 비교없이 수행하는 정렬 알고리즘이다.
끝자리부터 각 자릿수를 비교하여 정렬해나가는 방식으로 비교가 없다는 것이 특징이다.
유효숫자가 두개 이상인 경우, 모든 숫자요소에 대해서 수행될 때까지 각 자릿수에 대해서 반복된다.
=> 따라서, 전체 시간복잡도 : O(nw)(n은 숫자의 개수, w는 기수의 크기) 이다
기수란 기수법에서 말하는 수학적 용어로, 기수법(記數法, numeral system)은 수를 시각적으로 나타내는 방법인데, 기수법을 통해서 나타나는 각각의 숫자는 다른 수들과 구별되는 표기 방식을 가진다.
고대에는 각 나라별로 로마숫자, 그리스 숫자, 한자, 아라비아 숫자등이 사용되었지만 현대에 이르러서는 2진법, 10진법, 60진법등을 주로 사용하며, 대부분의 숫자는 10진법으로 표기된다.
따라서, 기수법은 쉽게 진법이라고 생각할 수 있다.
EX) 10진법의 숫자 10개
87, 487, 781, 100, 101, 0, 1, 512, 66, 24의 숫자들을 정렬한다고 생각해보자.
우선 기수정렬에는 기수 테이블의 크기만한 메모리가 더 필요하다.
기수테이블에는 각 진법에서 필요한 수들의 바구니가 있다고 생각하면 되는데,
지금의 예제에서는 10진법의 숫자들이므로 10진법에서 필요한 수인 0,1,2,3,4,5,6,7,8,9에 해당하는 바구니가 있다.
그림으로 보면, 이런식으로 진행된다.
이제 끝자리인 1의 자리부터 정렬을 해보자.
그러면, 각자 순서대로 1의 자리에 위치한 수와 동일한 바구니를 찾아가게 된다.
1의자리의 정렬이 완료되면, 0-9의 순서대로 다시 하나의 배열로 합친다.
다음으로는, 10의 자리수 정렬이 시작된다.
0, 1같은 경우에는 10의 자리수가 0이라고 생각하고 진행된다.
아 그림 하나씩 캡쳐해서 올리기 귀찮으.....
정렬이 되고난 후에는 다시 하나의 배열을 갖게 되고,
이후 100의 자리수 정렬이 시작되고, 100미만의 수들에 대해서는 100의 자리수가 0이라고 생각하고 진행된다.
마지막으로 100의 자리수에대해서도 0-9 순서로 하나의 배열로 합쳐주면,
짜잔- 정렬이 완료된다.
지금은 수의 최대값이 100의자리기 때문에 100의자리까지만 비교를 했지만, 만약 10억자리의 수가 포함된 10진법 10개라면, 최대 10억자리까지 비교를 해야 할 수도 있다.
EX) 2진법의 숫자 5개
다음으로는 컴퓨터가 주로 사용하는 진법인 2진법에 대해서 살펴보자.
5, 3, 4, 1, 2의 숫자들을 정렬한다고 생각해보자,
이 숫자들을 2진법으로 바꿔보면, 101, 011, 100, 001, 010가 된다.
이제 1의 자리수부터 바구니가 0과 1이 있다고 생각하고 진행하면 된다.
♠️ push_swap을 위한 radix sort를 구현
push_swap 과제에서는 우리는 스택A, 스택B만을 이용해야 하고, 명령어를 통해서 2번안에 접근가능한 인덱스는 top과 bottom 뿐이다.
그래서 독립적으로 생각하고 사용할 수 있는 메모리 공간이 A의 위, 아래 B의 위 아래 공간이 있다.
2진법으로 구현할 수도 있고, 3진법으로 구현할 수도 있었지만, 두 가지 방법 모두 계산해보니 2진법으로 구현했을 때의 방법이 명령어 사용개수의 최댓값이 적어서 2진법으로 정했다.
0바구니의 위치와 1바구니의 위치를 지정해준뒤 하나씩 돌려가며 해당 자리수가 0인지 1인지 확인하고, 옮겨주고, 모든 숫자에 대해서 확인이 끝나면 다시 A스택으로 옮기도록 했다.
이때, A의 위는 데이터를 빼내는 곳으로 사용하고, A의 아래는 1바구니를 저장하고, B의 위를 0바구니를 저장한다고 생각했다.
더 자세히 말하자면, 수를 shifting 연산과 bit연산을 이용해서,
for (All of stack_A)
{
if ((A->stack[A->top] >> i) & 1)
//ra command
else
//pb command
}i 번만큼 오른쪽으로 shift한 수가 1일 경우, ra를 하고, 0일 경우 pb를 하게 했다.
정리
요즘 대세는 push_swap을 퀵소트로 3개의 chunk씩 나눠서 푸는 것이지만 나는 스택이 2개면 2개의 메모리 공간을 이용하는 radix로 해야되지 않나? 에 꽂혀서 결국 여기까지 와버렸다...
열심히 명령어개수를 줄여보아도 100점받을 개수까지는 못줄여서 일단 평가를 진행할 예정이다.
이후에 기수정렬로 할 이 글을 읽고 있는 여러분들을 위해 최적화 아이디어 몇개를 써둔다.
이건 단지 아이디어일 뿐이므로, 원하는 정도의 효과를 내지 못할 수도 있다. 당연히...!
-
3,4,5개에 대해서도 하나의 알고리즘을 가진채 구현했다면, 해당 알고리즘에서 쓰는 명령어 개수보다 작은 개수로 정렬할 수 있는 집합에 대해서 하드코딩을 진행한다.
예를 들어, 2 1 3 4는 알고리즘으로 진행할 경우 5개의 명령어를 사용한다고 하면, 사실 사람이 보면 딱 sa만 하면 된다는걸 아니까. 이런경우들에 대해서 하드코딩해주면 명령어개수가 줄어들지 않을까? -
radix소트는 "기수"개수에 따라서 시간복잡도, 즉 push_swap에서 요구하는 명령어의 개수가 줄어들게 된다.
따라서, 큰 개수를 여러개의 작은 개수를 가진 chunk로 나눠서 각 chunk를 1-chunk개수로 세팅후 정렬한다.
500개를 정렬할 때 (1-500의 청크 1 개 -> 최대 9개의 기수(2^9 = 512) 1)에 대해서 정렬하는대신 (1- 100의 청크 5개 -> 7개의 기수에 대해 정렬(2^7 = 128) 5)로 을 줄일 수 있지 않을까??
-> 대신 이건 수를 변경하는 순간 원래의 수를 잃게 되므로 저장을 따로 해주던지..아니면 재귀를 이용해서 잘 스택 A에 순서대로 쌓는 방법을 고안하든 해야될듯. -
이건, @jibang님의 아이디어인데, radixsort를 하나의 기수에 대해서 진행하지 말고, 여러개의 기수를 묶어서 십진법을 비교해서 하면 어떨까하고 말씀해주셨다.
그러면 기수가 많을 경우 예를 들어 500 -> 기수가 9개 이면 3개/3개/3개로 나눠서 각각 3개짜리 기수에 대해서 radix sort를 진행한다. 각각 a의 바텀, b의 탑, b의 바텀으로 옮기고 거기서 다시 소팅을 해서 합치는 걸로 하면 어떨지...
