Merge sort

---

Merge sort

Divide and Conquer식 설계전략을 이용하고 추가적으로 통합하는 Combine과정을 거쳐셔 Merge sort를 진행한다.

이러한 방식을 하향식(top-down) 접근법이라고 한다.

위와 같이 주어진 배열을 계속 반으로 나누고 정렬을 진행하여 합하는 정렬 과정이다.

---

Source code

전체 code를 보기전에 psuedo code를 살펴보면 mergesort는 merge함수를 이용하였음을 알 수 있다.

mergesort 함수

 

 

merge 함수

전체 코드

mergesort.cpp

#include "ArrayVector.h"
#include <tuple>
#include <string>
#include <iostream>
#include <random>	//난수생성을 위한 library
#include <sstream>	//string으로 형변환을 위한 library
#include <chrono>	//실행시간 측정을 위한 library

using namespace std;

//divide and conquer방식으로 mergesort 함수 설계
void MergeSort(ArrayVector& vec, int L, int H, ArrayVector& sort_list) {
	//초기 조건
	if (L >= H)
		return;

	//divide
	int mid = (L + H) / 2;

	//conquer
	MergeSort(vec, L, mid, sort_list);
	MergeSort(vec, mid + 1, H, sort_list);

	//divide and conquer를 진행한후 sorting한 값들을 병합
	int i = L, j = mid + 1, temp = L;
	//L값을 대입해놓은 temp가 H보다 작거나 같을때까지 커지며 반복
	//미리 만들어둔 sort_list에 위치를 찾아서 하나하나 대입하여 sorting을 완성
	for (; temp <= H; ++temp) {
		if (j > H)
			sort_list[temp] = vec[i++];
		else if (i > mid)
			sort_list[temp] = vec[j++];
		else if (get<1>(vec[i]) <= get<1>(vec[j]))
			sort_list[temp] = vec[i++];
		else
			sort_list[temp] = vec[j++];
	}

	//sort_list를 vec에 복사
	for (int i = L; i <= H; ++i)
		vec[i] = sort_list[i];
}

//난수를 생성하기위한 메르텐 트위스트 함수 이용
random_device rd;
mt19937_64 gen(rd());

int main() {
	//실행 시간 측정을 위해 main문 시작지점 시간 측정
	auto start = std::chrono::system_clock::now();
	ArrayVector vec;
	string key;
	uniform_int_distribution<int> dis(0, 30000); // 0~1000사이 균등분포 선언

	for (int j = 0; j < 30000; j++)
	{
		int data = dis(gen);
		std::stringstream s;
		s << j;				//int값인 j를 string으로 변환가능 상태인 s로 변환
		key = "key" + s.str();           // key(숫자) 모양으로 key값 생성
		vec.insert(j, { key , data });	//값 insert
	}


	//before sorting
	cout << "before sorting" << endl;
	for (int i = 0; i < vec.size(); i++) {
		cout << "<" << get<0>(vec[i]) << ", " << get<1>(vec[i]) << ">" << endl;
	}
	//MergeSort 진행
	ArrayVector sort_list(30000);
	MergeSort(vec, 0, vec.size() - 1, sort_list);

	//after sorting
	cout << endl << "after sorting" << endl;
	for (int i = 0; i < vec.size(); i++) {
		cout << "<" << get<0>(vec[i]) << ", " << get<1>(vec[i]) << ">" << endl;
	}
	//실행 시간 측정을 위해 main문 종료직전 시간 측정
	auto end = std::chrono::system_clock::now();
	//시작시간과 종료시간의 차를 구해서 그 시간을 출력
	std::chrono::duration<double> elapsed_seconds = end - start;
	std::cout << "실행시간: " << elapsed_seconds.count() << " sec" << std::endl;
	return 0;
}

 

추가적으로 vector STL을 이용하지 않고 직접 구현한 Arrayvector header file과 cpp file을 첨부한다.

 

Arrayvector.h

#pragma once
#include <tuple>
#include <string>
#include <iostream>
using namespace std;

using Elem = tuple<string, int>;	//element를 <key,dat>쌍 튜플로 설정
class ArrayVector {
public:
	ArrayVector();		//생성자
	ArrayVector(int);	//0으로 채운 ArrayVector

	int size() const;	//element의 숫자
	bool empty() const;	//vector가 비었는지 확인하는 함수

	Elem& operator[](int i);	//연산자[] 오버로딩
	Elem& at(int i);			//인덱스 범위에 대한 예외처리

	void insert(int i, const Elem& e);	//특정 인덱스에 원소를 입력하는 함수
	void erase(int i);					//특정 인덱스 원소를 삭제하는 함수
	void reserve(int N);				//벡터 크기를 증가시키기 위한 함수
	int get_capacity();					//벡터의 크기를 return하는 함수

private:
	int capacity; // 벡터의 총 용량
	int n; // 벡터에 채워진 요소 개수
	Elem* A; // 튜플 원소
};

 

Arrayvector.cpp

#include "ArrayVector.h"
#include <iostream>
#include <stdexcept>
#include <tuple>	//tuple을 이용하기 위해 library이용

using namespace std;

//생성자 정의
ArrayVector::ArrayVector()
	: capacity(0), n(0), A(NULL) { }

// {"a",0} 으로 채워진 n개의 요소를 가지는 벡터
ArrayVector::ArrayVector(int n)
	: capacity{ n }, n{ }, A{ new Elem[n]{ } } {
	for (int i = 0; i < capacity; ++i)
		insert(i, { "a",0 });
}

//element의 숫자
int ArrayVector::size() const {
	return n;
}

//vector가 비었는지 확인하는 함수
bool ArrayVector::empty() const {
	return size() == 0;
}

//i인덱스의 원소를 출력하는 연산자[] 오버로딩
Elem& ArrayVector::operator[](int i) {
	return A[i];
}

//인덱스 범위에 대한 예외처리
Elem& ArrayVector::at(int i) {
	if (i < 0 or i >= n)
		throw invalid_argument("인덱스가 범위를 벗어났습니다.");
	return A[i];
}

//특정 인덱스에 원소를 입력하는 함수
void ArrayVector::insert(int i, const Elem& e) {
	if (n >= capacity) // 만약 n이 벡터 용량보다 크거나 같다면,
		reserve(max(1, 2 * capacity)); // 벡터의 크기를 원래 크기의 두배로 재조정

	for (int j = n - 1; j >= i; --j)	//i번째 인덱스부터 그 이후의 원소들을 한칸뒤로 이동
		A[j + 1] = A[j];

	A[i] = e;		//마련해둔 i번째 인덱스 자리에 e입력
	++n;
}

//특정 인덱스 원소를 삭제하는 함수
void ArrayVector::erase(int i) {
	for (int j = i + 1; j < n; ++j)	//i+1번째 인덱스부터 한칸씩 앞으로 덮어 씌워서
		A[j - 1] = A[j];			//자연스럽게 i번째 인덱스를 삭제
	--n;
}

//벡터 크기를 증가시키기 위한 함수
void ArrayVector::reserve(int N) {
	if (capacity >= N)	//capacity가 입력받은 N보다 크거나 같으면 유지
		return;

	//capacity가 입력받은 N보다 작을때
	Elem* B = new Elem[N];		//size가 N인 객체B 생성
	//A의 원소들을 B에 입력
	for (int j = 0; j < n; ++j)
		B[j] = A[j];
	//A를 삭제
	if (A != nullptr)
		delete[] A;

	A = B;		//A에 B를 다시 담아줌
	capacity = N;	//capacity를 N으로 설정
}

//벡터의 크기를 return하는 함수
int ArrayVector::get_capacity() {
	return capacity;
}

---

성능 분석

merge sort의 시간복잡도를 계산하면 다음과 같다.

divide and conquer 과정을 이용한 merge sort는 위와 같이 계산되고 결국 시간복잡도는 O(nlogn)으로 성능이 좋은 편에 속한다.

---