[알고리즘] LSD vs MSD in Radix sort (기수 정렬) / C++ 구현

Radix sort를 이해하려면, 먼저 Radix가 무엇인지를 알아야 한다.

이전 글의 Radix와 Key 부분까지는 알아야, Radix sort를 이해할 수 있다.

2021.06.12 - [분류 전체보기] - [알고리즘] LSD vs MSD in Radix sort (기수 정렬) / C++ 구현

 

Radix sort를 구현하는 방식은 몇가지가 있는데, 블로그에서는 LSD 와 MSD에 대해서 다루어 보려고 한다.

 

Radix sort는 여러자리의 수나 문자를 다룰 수 있기 때문에, 숫자 뿐만 아니라 string의 크기 또한 비교 가능하다.

 

LSD는 Last Significant Digit의 약자로, 가장 낮은 수부터 정렬하는 정렬방식을 말한다.

반면에, MSD 는 Most Significant Digit의 약자로, 높은 수부터 정렬하는 정렬 방식을 뜻한다.

우리가 보통 Radix Sort 라고 하면, LSD Radix Sort를 가리킨다. 그 이유는 LSD가 알고리즘이 일관되고 시간복잡도도 고정되어있기 때문이다.

 

먼저 LSD와 MSD를 Radix Sort를 통해 각각 공부하고, 두 방법의 차이점을 정리해보겠다.

 

---

1. LSD Radix Sort

LSD Radix Sort 는 아래 그림에서 보듯이, 가장 낮은 Radix(기수)부터 정렬을 하는 방식이다.

 

먼저 코드를 살펴보자.

void				lsd_string_radix(string array[], int array_size, int max_chars)

LSD radix sort의 string은 다음과 같다.

여기서 array[] 는 정렬하고 싶은 단어들의 배열이고, array_size는 단어의 개수이다. 그리고 max_char은 단어의 크기이다.

 

 

 

만약에 우리가 paris, seoul, viena 이렇게 세개의 단어를 정렬하고 싶다고 하자.

 

첫 번째로 우리는 빈 배열을 하나 만들어야 한다. 배열의 크기는 단어의 개수 만큼 만들면 된다. (원래 array의 크기와 같다.)

	string			*temp = new string[array_size];

 

 

 

이제 우리는 paris의 s, seoul의 l, viena의 a부터 비교를 하면 된다.

그 다음 비교값은 i와 u와 n이 될 것이다.

이렇게 뒤에서부터 하나씩 비교하는 처리를 다음 for문 안에서 하게 될 것이다.

	for (int i = max_chars - 1; i >= 0; i--)
	{

	}

 

 

이제 이 안에서 각각 계수 정렬을 할  것이다. Radix 단원에서 보고 왔겠지만 계수 정렬에서 필요한 것은 각각 Radix를 count해주는 배열이다.

const int R = strlen("abcdefghijklmnopqrstuvwxyz") + 1;

for (int i = max_chars - 1; i >= 0; i--)
{
	int count[R] = {0, };
}

여기서 R은 Radix 총 개수 + 1인데, 이는 계수 정렬에서 봤겠지만, 우리가 count에 넣고 싶은 것은 개수가 아니라 시작 index이기 때문이다.

 

 

 

준비가 다 됐으면, 다음과 같이 계수 정렬을 실행해주면 된다.

계수정렬을 잘 모르겠다면, 반드시 앞에서 링크를 걸어둔 계수 정렬에 대해서 읽고 오자. 그 계수 정렬과 표현만 다르지 매커니즘은 똑같다.

for (int i = max_chars - 1; i >= 0; i--)
{
	int count[R] = {0, };

	for (int j = 0; j < array_size; j++)
		count[static_cast<int>(array[j][i]) - 'a' + 1]++;

	for (int j = 2; j < 26; j++)
		count[j] += count[j - 1];

	for (int j = 0; j < array_size; j++)
		temp[count[static_cast<int>(array[j][i]) - 'a']++] = array[j];

	for (int j = 0; j < array_size; j++)
		array[j] = temp[j];
}

 

 

전체 코드

#include <iomanip>
#include <iostream>
#include <string>

using namespace std;

const int R = strlen("abcdefghijklmnopqrstuvwxyz") + 1;

void				lsd_string_radix(string array[], int array_size, int max_chars)
{
	string			*temp = new string[array_size];

	for (int i = max_chars - 1; i >= 0; i--)
	{
		int count[R] = {0, };

		for (int j = 0; j < array_size; j++)
			count[static_cast<int>(array[j][i]) - 96]++;

		for (int j = 2; j < 26; j++)
			count[j] += count[j - 1];

		for (int j = 0; j < array_size; j++)
			temp[count[static_cast<int>(array[j][i]) - 97]++] = array[j];

		for (int j = 0; j < array_size; j++)
			array[j] = temp[j];
	}
}

int					main()
{
	string			array[6] = {"paris", "seoul", "viena", "nizza", "praha", "busan"};

	lsd_string_radix(array, 6, 5);
	for (size_t i = 0; i < 6; i++)
		cout << array[i] << endl;
	return 0;
}

 

 

LSD Radix Sort 시간복잡도

시간 복잡도는 매우 작다. 어차피 총 단어의 개수가 N개이고, 단어의 길이가 W라고 하면, 그냥 하나씩 count 해서 옮기기만 하면 되기 때문에 O(N * W)의 시간 복잡도를 가진다. 여기서 W는 어차피 상수이기 때문에 최종적으로 다음과 같은 시간복잡도를 가지게 된다.

 

O(N)

 

LSD Radix Sort 공간복잡도

 

공간복잡도는 큰 편이다. 우리는 count 배열과 정렬된 배열을 임시로 저장할 N크기만큼의 배열도 필요하다.

즉, V() + N 만큼의 공간이 필요한데, 여기서 V() 역시 상수이기 때문에 공간 복잡도는 다음과 같다.

 

 

O(N)

 

---

 

2. MSD Radix Sort

 

MSD Radix Sort는 정렬하고싶은 배열의 앞부분부터 계수 정렬을 시행하는 정렬이다.

재귀적으로 앞부분부터 뒷부분을 정렬해나가는 방식이 많이 쓰인다.

 

코드를 한번 살펴보자.

LSD 코드와 같은 부분은 따로 설명하지 않겠다.

 

눈 여겨 봐야 할 부분은 재귀가 어떻게 이루어지는 지이다.

다음은 재귀적으로 이루어지는 함수의 선언부이다.

여기서 array와 aux는 각각 무엇을 의미하는 지 알 것이다.

lo는 재귀함수로 들어갈 단어의 첫번째 인덱스이고, hi는 재귀함수로 들어갈 단어의 마지막 인덱스이다.

예를들어 paris와 praha를 비교한다면, p를 의미하는 count 배열 (count[10])의 값은 K가 될 것이다. (k는 o의 마지막 인덱스 + 1)

그리고 p가 두개이기 때문에 q가 시작하는 인덱스는 K+2이 될 것이다.

결국 p에 대해서 재귀로 넘어갈 때는, lo = lo + k, hi = lo + k + 2 - 1 이 될 것이다. 그리고 이제 두번째 글자를 비교해야 하기 때문에 d = d + 1이 된다.

void				sort(string array[], string aux[], int lo, int hi, int d)

 

전체 코드

#include <iostream>
#include <string>

using namespace std;

const int R = strlen("abcdefghijklmnopqrstuvwxyz") + 1;
const int N = 8;

// low는 첫번째 단어, hi는 마지막 단어의 index
void				sort(string array[], string aux[], int lo, int hi, int d)
{
	int count[R] = {0, };

	// 해당 카운트의 글자 수가 0개이면 끝낸다.
	if (hi <= lo)
		return ;
	
    // 기존의 계수 비교법과 같음.
	for (int i = lo; i <= hi; i++)
		count[static_cast<int>(array[i][d]) - 'a' + 1]++;
	for (int r = 0; r < R + 1; r++)
		count[r + 1] += count[r];
	for (int i = lo; i <= hi; i++)
		aux[count[static_cast<int>(array[i][d]) - 'a']++] = array[i];
	for (int i = lo; i <= hi; i++)
		array[i] = aux[i - lo];
	
    // 범위 하나씩 재귀
	for (int r = 0; r < R; r++)
		sort(array, aux, lo + count[r], lo + count[r + 1] - 1, d + 1);
}

void				MSDSort(string array[])
{
	string *aux = new string[N];
	sort(array, aux, 0, N - 1, 0);
}

int					main(void)
{
	string			array[N] = {"praha", "seoul", "milan", "viena", "paris", "busan", "kimpo", "jaeju"};

	MSDSort(array);
	for (int i = 0; i < N; i++)
		cout << array[i] << endl;
}

 

MSD Radix Sort 시간복잡도

시간 복잡도는 매우 작다. 어차피 총 단어의 개수가 N개이고, 단어의 길이가 W라고 하면, 그냥 하나씩 count 해서 옮기기만 하면 되기 때문에 O(N * W)의 시간 복잡도를 가진다. 여기서 W는 어차피 상수이기 때문에 최종적으로 다음과 같은 시간복잡도를 가지게 된다.

다만 앞자리부터 비교하기 때문에 두 수를 비교할 때는 끝까지 가지 않고도 대소 관계가 결정될 수 있다. 이 경우에는 훨씬 적은 시간 복잡도를 가진다.

 

O(N)

 

MSD Radix Sort 공간복잡도

 

공간복잡도는 큰 편이다. 우리는 count 배열과 정렬된 배열을 임시로 저장할 N크기만큼의 배열도 필요하다.

즉, (w * V()) + N 만큼의 공간이 필요한데, 여기서 V() 역시 상수이기 때문에 공간 복잡도는 다음과 같다.

 

 

O(N)