백준 2751번 merge sort c++

수 정렬하기2

O(nlogn)만 통과가되므로

Advanced Sorting Algorithm을 써야한다

병합정렬,퀵정렬,힙정렬이 있는데

나는 병합정렬을 선택했다

 

divide부분은 이 수도코드를 참고했다

q=(p+r)/2

q,p,r로 보면 헷갈리니

p=start, q=mid, r=end라고 보면 된다

mergeSort(A,start,mid);

mergeSort(A,mid+1,end);   이부분이 divide의 핵심이다

mid를 기준으로 왼쪽 오른쪽을 재귀적으로 호출해

배열을 분리하고

merge(A,start,mid,end)를 호출해

병합 및 정렬을 한다

 

 

병합 및 정렬은 이 자료를 참고했다

이 자료를 다시 보게 될 줄이야..

교수님 말 틀린 거 없다

 

조금 설명하자면 int i,j,k 보통 이 세 개의 변수로 index를 control하는데

i는 병합 전 배열의 start~mid까지의 index담당

j는 병합 전 배열의 mid~end까지의 index 담당

k는 정렬된 값들을 저장할 배열의 index를 담당

 

그래서

a[i]와 a[j]값을 비교해

더 작은값을 결과값 배열(result라고하겠다)

result[k++]=a[i++] or result[k++] a[j++] 저장시켜준다

그런데

반복문을 돌다보면

i만 먼저 끝내버리거나 j만 먼저 끝내버릴 수 있기때문에

뒤에 한 번더 반복문을 돌려준다

그러면 merge sort가 끝나게 된다

 

 

 

https://blog.naver.com/rys0603/221155999507

Merge Sort 머지소트 C++

이 분 코드를 많이 참고했다

2751번의 요구사항에 맞게 조금 수정하고

내가 이해한 내용을 주석으로 추가했다

 

내 코드

#include <iostream>
#define SIZE 1000001
using namespace std;

int arr[SIZE];		//sort된 배열 저장


void Divide(int*, int, int);	//divide
void MergeSort(int*, int, int);			//conquer and merge



int main() {

	int n;
	cin >> n;
	int* a = new int[n];

	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}

	Divide(a, 0, n - 1);


	for (int i = 0; i < n; i++) {
		cout << a[i] << "\n";			//endl하면 느려지기때문에 "\n"사용
	}


	return 0;
}

void Divide(int* a, int start, int end) {
	if (start < end) {		//start가 각 divde한 배열 첫번째 index, end가 마지막 index
							//start<end여야지만 divde and conquer하도록 조건생성
		int mid = (start + end) / 2;
		Divide(a, start, mid);		//절반씩 divide
		Divide(a, mid + 1, end);
		MergeSort(a, start, end);		//start~end까지 mergesort
	}
}

void MergeSort(int* a, int start, int end) {
	int mid = (start + end) / 2;

	int i = start, j = mid + 1, k = start;		//i는 a배열의 start~mid까지 
												//j는 a배열의 mid+1~end까지 담당
												//k는 arr배열(sort된 값 저장) 담당

	while (i <= mid && j <= end) {
		if (a[i] <= a[j])
			arr[k++] = a[i++];		//더 작은걸 먼저 저장함
		else
			arr[k++] = a[j++];
	}

	while (i <= mid)			//한쪽이 먼저 소진된 경우 나머지 복사
		arr[k++] = a[i++];
	while (j <= end)
		arr[k++] = a[j++];

	for (int i = start; i <= end; i++)
		a[i] = arr[i];				//정렬된 값 a에 저장
}

살짝 강의자료랑 다른점은

마지막에 정렬된 값을 저장한 arr의 값을

다시 a에 저장해준다

 

 

 

그리고 다시 printf, cout, endl, "\n"간의 관계

출력을 cout, endl로 하면 시간초과가뜬다

cout, "\n"으로 한게 printf,"\n"보다 빠르다

그래서 merge sort로 했는데 시간 초과가 뜬다면

endl을 "\n"으로 바꿔서 제출하면 된다

 

 

 

+

merge sort말고

c++ stl sort함수 활용방법

출처 : https://cryptosalamander.tistory.com/45

[백준 / BOJ] - 2751번 수 정렬하기2 C++ 풀이

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
    int num,tmp;
    vector<int> a;
    cin >> num;
    for(int i = 0; i < num; i++)
    {
        cin >> tmp;
        a.push_back(tmp);
    }
    sort(a.begin(),a.end());
    for(int i = 0; i < num; i++)
        cout << a[i] << '\n';
}

int 자료형으로 vector를 하나 만들고

수를 하나씩 입력받아 vector에다 push 한 후,

sort를 해주면 알아서 o(nlogn)시간 안에 정렬해주는거같다

매우 편리한듯