[Algorithm] Merge Sort 구현하기
업데이트(2018.04.19): C++ 정렬 코드 추가
Merge Sort를 구현해보자
환경
- Python
- C++
Merge Sort란?
원리
- 현재 주어진 값들을 반으로 나누고 각각 나누어진 부분을 또 계속 나눈 후에 합치면서 정렬을 진행한다. 대표적인
분할정복의 예제
특징
Divide and Conquer이라는 분할정복 방법으로 정렬을 진행하며 자세한 부분은 다음을 참고하시면 좋습니다.stable sort: 정렬 할 원소들이 튜플이나 레코드처럼 다른 원소들을 포함하고 있을 때 정렬 후에도 그 순서가 유지되는 정렬입니다.
복잡도
- 시간복잡도:
O(nlogn) - 공간복잡도: 이 코드에서는
O(n)이며 분할정복을 병렬로 진행하면O(nlogn)
구현 코드(Python)
def merge_sort(A):
if len(A) <= 1:
return A
# 분할 정복
mid = int(len(A)/2)
left_side = merge_sort(A[:mid])
right_side = merge_sort(A[mid:])
# left,right 각각을 위한 인덱스 l,r
# 왼쪽과 오른쪽에서의 합병된 값을 저장할 A의 인덱스 k
l = 0
r = 0
k = 0
# 이제 왼쪽과 오른쪽을 비교하면서 merge
while l < len(left_side) and r < len(right_side):
if left_side[l] < right_side[r]:
A[k] = left_side[l]
k += 1
l += 1
else:
A[k] = right_side[r]
k += 1
r += 1
# 이제 남아 있는 경우만 더 확인
# 오른쪽이 남아있다면
while r < len(right_side):
A[k] = right_side[r]
r += 1
k += 1
# 왼쪽이 남아있다면
while l < len(left_side):
A[k] = left_side[l]
l += 1
k += 1
return A
import random
A = [random.randint(0,100) for _ in range(0,10)]
print(A)
merge_sort(A)
print(A)
구현 코드(C++)
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <time.h>
#include <vector>
using namespace std;
void merge_sort(vector<int> &a, int left, int right) {
if (left < right) {
// 분할 정복
int mid = left + (right - left) / 2;
merge_sort(a, left, mid);
merge_sort(a, mid + 1, right);
//merge(a, left, mid, right);
// i는 왼쪽, j는 오른쪽, k는 a를 채울 index
int i, j, k;
int left_side_size = mid - left + 1; // left ~ mid
int right_side_size = right - mid; // mid+1 ~ right
// 왼쪽과 오른쪽을 저장할 배열 1개씩 생성
int * left_side = (int*)malloc(left_side_size * sizeof(int));
int * right_side = (int*)malloc(right_side_size * sizeof(int));
// 배열 채우고
for (int l = 0; l < left_side_size; l++) {
left_side[l] = a[left + l];
}
for (int r = 0; r < right_side_size; r++) {
right_side[r] = a[mid + 1 + r];
}
// Merge
// 이제 양 옆에서 하나씩 비교하면서 a에 추가
i = j = 0;
k = left;
while (i < left_side_size && j < right_side_size) {
if (left_side[i] <= right_side[j]) {
a[k] = left_side[i];
i++;
}
else {
a[k] = right_side[j];
j++;
}
k++;
}
// 오른쪽이 남아있다면
while (j < right_side_size) {
a[k] = right_side[j];
j++;
k++;
}
// 왼쪽이 남아있다면
while (i < left_side_size) {
a[k] = left_side[i];
i++;
k++;
}
free(left_side); free(right_side);
}
}
int main() {
vector<int> a(5);
int len = a.size(); // 벡터길이
// 랜덤함수를 위한 srand와 seed
srand(time(NULL));
// 벡터 초기화
for (int i = 0; i < len; i++) {
// 1 ~ 50까지의 난수 생성
a[i] = rand() % 50 + 1;
}
// 정렬 전 출력
for (int i = 0; i < len; i++) {
cout << a[i] << ' ';
}
cout << '\n';
// 합병정렬
merge_sort(a, 0, len - 1);
// 정렬 후 출력
for (int i = 0; i < len; i++) {
cout << a[i] << ' ';
}
cout << '\n';
return 0;
}