[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;
}


참고자료

[Linux] 쉘 스크립트에서 멀티프로세스(혹은 스레드) 기능 사용하기

> 백그라운드로 명령어를 실행해서 병렬적으로 실행되는 멀티 프로세스 환경을 만들어보자.## 환경- Linux 기반 시스템- Bash shell(/bin/bash)## 멀티프로세스? 병렬처리? 멀티스레드? 백그라운드 프로세스?- 여기서 진행할 방식...… Continue reading