[Do it! 알고리즘 코딩테스트: Chapter 4. 정렬(Sort)] 병합 정렬(Merge Sort), 기수 정렬(Radix Sort)

본 포스팅은 Do it! 알고리즘 코딩테스트: C++편을 토대로 공부한 내용을 정리하기 위한 포스팅입니다.

https://github.com/KwonKiHyeok/Do_it_Alogrithm_Coding_Test_with_Cpp

GitHub - KwonKiHyeok/Do_it_Alogrithm_Coding_Test_with_Cpp: Do it! 알고리즘 코딩 테스트: C++편

 

 

 

1. 병합 정렬(Merge Sort)

 병합 정렬(Merge Sort)은 분할 정복(Divide and Conquer) 알고리즘을 사용하는 정렬 방법이다. 배열을 반으로 나누고, 각각을 정렬한 후, 다시 병합하면서 정렬을 완료한다.

 

알고리즘 과정

1. 분할(Divide)
   정렬할 배열을 중간 기준으로 두 개의 하위 배열로 나눈다.
2. 정복(Conquer)
   각 하위 배열을 재귀적으로 병합 정렬하여 정렬된 상태로 만든다.
3. 병합(Merge)
   정렬된 두 개의 하위 배열을 하나의 정렬된 배열로 합친다

시간 복잡도

• 최선, 평균, 최악의 경우: O(nlogn) 모든 경우에서 같은 시간 복잡도를 가진다.
• 공간 복잡도: 추가적인 배열을 사용하므로 O(n)의 공간을 필요로 한다.

 

// Baekjoon Online Judge Problem. 2751

#include <iostream>
#include <vector>
using namespace std;

vector<int> merge_sort(vector<int>& arr, int left, int right);
vector<int> merge(vector<int>& left_arr, vector<int>& right_arr);

int main() {

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);


	int N;
	cin >> N;

	vector<int> arr(N);
	vector<int> temp(N, 0);

	for (int i = 0; i < N; i++)
		cin >> arr[i];

	vector<int> result = merge_sort(arr, 0, arr.size() - 1);

	for (int i = 0; i < N; i++)
		cout << result[i] << '\n';

	return 0;

}

vector<int> merge_sort(vector<int>& arr, int left, int right) {
	
	if (left == right)
		return vector<int>{arr[left]};
	
	int mid = (left + right) / 2;
	vector<int> left_arr = merge_sort(arr, left, mid);
	vector<int> right_arr = merge_sort(arr, mid + 1, right);
	
	return merge(left_arr, right_arr);
}

vector<int> merge(vector<int>& left_arr, vector<int>& right_arr) {
	
	vector<int> result;
	int i = 0, j = 0;
	
	while (i < left_arr.size() && j < right_arr.size()) {

		if (left_arr[i] < right_arr[j]) {
			result.push_back(left_arr[i]);
			i++;
		}
		else {
			result.push_back(right_arr[j]);
			j++;
		}
	}

	while (i < left_arr.size()) {
		result.push_back(left_arr[i]);
		i++;
	}
	while (j < right_arr.size()) {
		result.push_back(right_arr[j]);
		j++;
	}

	return result;
}

 

 

#include<iostream>
#include<vector>
using namespace std;

void merge_sort(int start, int end);
vector<int> merge(vector<int>& left_v, vector<int>& right_v);
static vector<int> tmp;
static vector<int> myVector;
static long answer;

int main() {

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);


	int N;
	cin >> N;
	myVector = vector<int>(N + 1, 0);
	tmp = vector<int>(N + 1, 0);

	for (int i = 1; i <= N; i++) {
		cin >> myVector[i];
	}

	answer = 0;
	merge_sort(1, N);
	cout << answer << '\n';
	return 0;
}

void merge_sort(int start, int end) {

	if (end - start < 1) {
		return;
	}

	int mid = start + (end - start) / 2;

	merge_sort(start, mid);
	merge_sort(mid + 1, end);

	for (int i = start; i <= end; i++) {
		tmp[i] = myVector[i];
	}

	int k = start;
	int i = start, j = mid + 1;

	while (i <= mid && j <= end) {
		if (tmp[i] > tmp[j]) {
			myVector[k] = tmp[j];
			answer = answer + j - k;
			k++, j++;
		}
		else {
			myVector[k] = tmp[i];
			k++, i++;
		}
	}

	while (i <= mid) {
		myVector[k] = tmp[i];
		k++, i++;
	}

	while (j <= end) {
		myVector[k] = tmp[j];
		k++, j++;

	}
}

 

병합 정렬하는 과정에서 뒤쪽 그룹의 원소가 앞쪽 그룹으로 이동하게 되면, 이는 버블 정렬에서 swap을 여러번 한 효과와도 같다. (j - k)만큼의 swap 효과. 

 이 문제의 핵심은 앞쪽 그룹은 신경쓰지 않고, 오른쪽 그룹이 이동하는 것만 신경써서 합하면 해결할 수 있는 문제이다.

 

 

2. 기수 정렬(Radix Sort)

 기수 정렬(Radix Sort)은 정렬할 숫자를 자릿수별로 비교하여 정렬하는 알고리즘이다. 일반적으로 자릿수가 가장 낮은 자리(일의 자리)부터 높은 자리(최고 자리)까지 순차적으로 정렬을 수행한다.

 

 

기수 정렬의 동작 과정

1. 최대 자릿수 확인: 정렬할 숫자들 중에서 가장 큰 숫자의 자릿수를 확인한다.
2. 자릿수별 정렬: 일의 자리부터 시작하여 각 자릿수를 기준으로 안정 정렬(주로 계수 정렬 또는 버킷 정렬)을 수행한다.
3. 반복: 자릿수를 한 단계씩 올려가며 정렬을 수행한다.
4. 완료: 가장 높은 자릿수까지 정렬이 끝나면 최종적으로 정렬된 배열이 완성된다.

 

시간 복잡도

 O(d * (n + k))

• d: 숫자의 최대 자릿수
• n: 정렬할 요소 개수
• k: 기수(0~9의 경우 10)

 

// Baekjoon Online Judge Problem. 10989

#include<iostream>
using namespace std;

int main() {

	ios::sync_with_stdio(0);
	cin.tie(NULL);
	cout.tie(NULL);


	int N;
	cin >> N;
	int arr[10001] = { 0 };
	int number = 0;

	for (int i = 0; i < N; i++) {
		cin >> number;
		arr[number]++;
	}

	for (int i = 0; i <= 10000; i++) {

		if (arr[i] != 0) {
			for (int j = 0; j < arr[i]; j++) {
				cout << j << '\n';
			}
		}
 	}
	
	return 0;
}