[C++ STL과 알고리즘] 벡터의 merge sort 공부하기

 

 

Merge Sort?

: 주어진 문제를 반으로 분할하고 해결한 뒤 다시 병합하는 분할 정복 알고리즘  

---

https://www.youtube.com/watch?v=ctkuGoJPmAE

나동빈님의 merge sort 튜토리얼을 보고 merge sort 배열의 구현에는 성공했다. 

다음 단계로, 벡터 컨테이너 클래스로 merge sort를 구현하는 것을 시도했다.

 

#include <iostream>
#include <vector>
#include <string>
#include <algorithm> 

using namespace std;

vector<int>sorted; //정렬된 데이터를 저장할 벡터 선언

/* 
i: 분할 후 왼쪽 리스트
j: 분할 후 오른쪽 리스트
k: 복사할 배열의 인덱스
*/

void merge(vector<int>& v, int start, int mid, int end)
{	
	int i = start;
	int j = mid + 1; //분할한 지점 +1의 인덱스
	int k = start; //시작 지점

	//작은 순서대로 삽입
	while (i <= mid && j <= end) // 중간점과 배열의 끝 전에 닿기까지 진행
	{
		if (v[i] <= v[j]) {
			sorted[k] = v[i];
			i++;
		}
		else { // a[i] > a[j]
			sorted[k] = v[j];
			j++;
		}
		k++;
	}

	int entry = (i > mid) ? j : i;
	int target = (i > mid) ? end : mid;

	for (int t = entry; t <= target; ++t)
	{
		sorted[k] = v[t];
		k++;
	}
	//임시리스트를 원래 리스트에 복사
	for (int t = start; t <= end; t++) v[t] = sorted[t];
}

void mergeSort(vector<int>& v, int start, int end) {
	if (sorted.size() == 0) sorted = vector<int>(v.size());
	if (start < end) {
		int mid = (start + end) / 2;
		mergeSort(v, start, mid);
		mergeSort(v, mid+1, end);
		merge(v, start, mid, end);
	}
}


int main() {
	int n;
	cin >> n;
	vector<int> v(n);
	for (int i = 0; i < n; i++)
	{
		cin >> v[i];
	}
	mergeSort(v, 0, v.size() - 1);
	for (const auto& e:v) //벡터 v의 element를 반복자를 쓴 것처럼 호출..
	{
		cout << e;
	}
}

 

https://velog.io/@cgotjh/%EB%B3%91%ED%95%A9-%EC%A0%95%EB%A0%ACMerge-Sort

https://blockdmask.tistory.com/384

http://www.cplusplus.com/forum/beginner/252949/

const auto& for loop - C++ Forum

merge와 mergeSort의 매개변수로 벡터를 받을 때, 참조자를 붙이자. 그렇게하고 나면, 따로 정렬한 벡터를 반환하거나 하지 않아도 v[t] = sorted[t]라는 for loop를 통해서, 정렬한 element 값들이 vector에 자리를 찾아가게 된다. 

main함수에서 auto 키워드로 for loop statement cin >> elem은 불가능