글 읽기 - 병합 정렬 어디가 틀린걸까요 ㅠㅠ

psj1028 5년 전 0

5 4 3 2 1

넣으면

2 1 5 4 3

으로 출력이 되길래 고민을 계속 해도 어디가 틀렸는지 감이 안 잡힙니다 ㅠㅠ..

#include <iostream>
#include <algorithm>
using namespace std;
int a[1000000];
int ans[1000000];

void merge_sort(int first, int last) {
	int i, j, k;
	int mid = (first + last) / 2;
	if (first < last) {
		
		merge_sort(first, mid);
		merge_sort(mid + 1, last);
		//merge
		for (k = first, i = first, j = mid + 1; i<= mid && j <= last;) {
			if (a[i] < a[j]) {
				ans[k++] = a[i++];
			}
			else {
				ans[k++] = a[j++];
			}
		}
		while (i <= mid)
			ans[k++] = a[i++];

		while (j <= last)
			ans[k++] = a[j++];

	}
}
int main() {
	int n;
	scanf("%d", &n);
	for (int i = 0; i<n; i++) {
		scanf("%d", &a[i]);
	}
	merge_sort(0, n - 1);
	for (int i = 0; i<n; i++) {
		printf("%d\n", ans[i]);
	}
	return 0;
}

매번 merge_sort 함수가 호출될 때마다 ans에 이미 절반씩 부분 정렬된 a의 원소들을 앞에서부터 순서대로 비교하면서 이어붙이는 것이 병합 정렬입니다. 그런데 여기서는 a의 원소들은 일절 변경하지 않고 ans에 값을 옮기기만 하니, 함수가 종료된 후에 a는 정렬이 되지 않은 상태입니다. 그 상태로 다시 더 큰 구간에 기존의 a의 순서를 유지하면서 비교해서 넣어도, 전체가 정렬된다는 보장이 없습니다.

psj1028 5년 전 0

감사합니다! 이해했습니다 ㅎㅎㅎ

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

병합 정렬 어디가 틀린걸까요 ㅠㅠ

psj1028 5년 전 0

djm03178 5년 전 1

psj1028 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말