[C++] 백준 2751 수 정렬하기 - 재귀, 병합정렬

2020. 12. 3. 00:27·Algorithm/Baekjoon
#include <iostream>
#include <vector>

using namespace std;
vector<int> num;
vector<int> tempNum;

void MergeDivied(vector<int> *list, int left, int right);
void MergeSort(vector<int> &list, int left, int mid, int right);

int main()
{
	int n = 0;
	cin >> n;
	
	for (int i = 0; i < n; i++)
	{
		int temp = 0;
		cin >> temp;
		num.push_back(temp);
		tempNum.push_back(0);
	}

	MergeDivied(&num, 0, n - 1);

	for (int i = 0; i < n; i++)
	{
		cout << num[i] << "\n";
	}
}

void MergeDivied(vector<int> *list, int left, int right)
{
	if (left == right) return;

	int mid = 0;

	if (left < right)
	{
		mid = (left + right) / 2;
		MergeDivied(list, left, mid);
		MergeDivied(list, mid + 1, right);

		MergeSort(*list, left, mid, right);
	}
}

void MergeSort(vector<int> &list, int left, int mid, int right)
{
	int L, R, k, a;
	L = left;
	R = mid + 1;
	k = left;

	//왼쪽 항과 오른쪽 항의 비교하여 하나씩 대입
	while (L <= mid && R <= right)
		tempNum[k++] = list[L] <= list[R] ? list[L++] : list[R++];

	//남은 수를 대입 
	if (L > mid)
		for (a = R; a <= right; a++)
			tempNum[k++] = list[a];
	else
		for (a = L; a <= mid; a++)
			tempNum[k++] = list[a];

	//원래 배열에 저장
	for (a = left; a <= right; a++)
		list[a] = tempNum[a];
}

 


처음에 배열의 개수만큼 정렬한 수를 넣을 배열의 빈 공간을 만들어줍니다.

for (int i = 0; i < n; i++)
	{
		int temp = 0;
		cin >> temp;
		num.push_back(temp);
		tempNum.push_back(0);
	}

 

주소로 보내어 값이 변동하게 합니다.

MergeDivied(&num, 0, n - 1);

 

함수는 포인터로 해주어 주소를 받아줍니다.

void MergeDivied(vector<int> *list, int left, int right)

 

재귀함수로 반복합니다.

반복하면서 아래의 정렬을 할 함수를 통해 정렬을 합니다.

[재귀순서 아래 더보기 참고]

더보기

https://gmlwjd9405.github.io/2018/05/08/algorithm-merge-sort.html

 

[알고리즘] 합병 정렬(merge sort)이란 - Heee's Development Blog

Step by step goes a long way.

gmlwjd9405.github.io

https://www.youtube.com/watch?v=FCAtxryNgq4&ab_channel=%EC%BD%94%EB%94%A9%ED%95%98%EB%8A%94%EA%B1%B0%EB%8B%88

 

void MergeDivied(vector<int> *list, int left, int right)
{
	if (left == right) return;

	int mid = 0;

	if (left < right)
	{
		mid = (left + right) / 2;
		MergeDivied(list, left, mid);
		MergeDivied(list, mid + 1, right);

		MergeSort(*list, left, mid, right);
	}
}

 

왼쪽 항과 오른쪽 항의 값을 비교하여 빈 배열에 하나씩 넣어줍니다.

L일 경우 다음항으로 넘어가기 위해 1씩 증가시키다가 mid와 L의 값이 같아지면 L쪽은 정렬이 되고 while문을 나갑니다.

void MergeSort(vector<int> &list, int left, int mid, int right)
{
	int L, R, k, a;
	L = left;
	R = mid + 1;
	k = left;

	//왼쪽 항과 오른쪽 항의 비교하여 하나씩 대입
	while (L <= mid && R <= right)
		tempNum[k++] = list[L] <= list[R] ? list[L++] : list[R++];

	

 

남은 정렬이 되지 않은 수를 차례로 정렬해줍니다. 

남은것이 L쪽이면 남은 L번째의 수부터 mid 중간까지 하나씩 넣어줍니다.

다 마치면 원래 배열에 정렬된 배열을 넣어줍니다.

//남은 수를 대입 
	if (L > mid)
		for (a = R; a <= right; a++)
			tempNum[k++] = list[a];
	else
		for (a = L; a <= mid; a++)
			tempNum[k++] = list[a];

	//원래 배열에 저장
	for (a = left; a <= right; a++)
		list[a] = tempNum[a];
}

 

저작자표시 (새창열림)

'Algorithm > Baekjoon' 카테고리의 다른 글

[C++] 백준 11651 좌표 정렬하기 2  (0) 2021.01.06
[C++] 백준 11650 좌표 정렬하기  (0) 2020.12.07
[C++] 백준 10989 수 정렬하기 - 계수정렬(Counting Sort)  (0) 2020.12.04
[C++] 백준 11729 하노이 탑 - 재귀  (0) 2020.11.12
[C++] 백준 10872 팩토리얼 - 재귀  (0) 2020.11.10
'Algorithm/Baekjoon' 카테고리의 다른 글
  • [C++] 백준 11650 좌표 정렬하기
  • [C++] 백준 10989 수 정렬하기 - 계수정렬(Counting Sort)
  • [C++] 백준 11729 하노이 탑 - 재귀
  • [C++] 백준 10872 팩토리얼 - 재귀
chanheess
chanheess
'왜' 그렇게 했는가?에 대한 생각으로 공부 및 작업의 저장관리
왜 그렇게 생각했는가?'왜' 그렇게 했는가?에 대한 생각으로 공부 및 작업의 저장관리
  • chanheess
    왜 그렇게 생각했는가?
    chanheess
  • 전체
    오늘
    어제
    • 분류 전체보기
      • Backend Programming
      • Game Programming
        • Unreal
        • DirectX
      • C++
        • Memo
        • Basic
        • Effective Modern
      • Java
      • Algorithm
        • Memo
        • Baekjoon
        • Programmers
        • HackerRank, LeetCode
      • Data Structure
      • Design Pattern
      • Etc
        • Memo
        • Daily Log
        • Book
  • 최근 글

  • 최근 댓글

  • 태그

    티스토리챌린지
    프로그래머스
    Java
    dp
    JPA
    오블완
    위클리 챌린지
    JWT
    백준
    알고리즘
    spring
    c++ 기초 플러스
    SpringSecurity
    dfs
  • hELLO· Designed By정상우.v4.10.0
chanheess
[C++] 백준 2751 수 정렬하기 - 재귀, 병합정렬

개인정보

  • 티스토리 홈
  • 포럼
  • 로그인
상단으로

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.