글 읽기 - [C] Merge Sort 어떤 부분 때문에 틀렸는지 좀 봐주세요.

akdlzhf2008 2년 전 0

아래와 같이 코드를 작성했습니다.

제가 어떤 요소를 간과한 것인지 알고 싶습니다.

#include <stdio.h>

int number;
int sorted[1000001];
int data[1000001];

void Merge(int a[], int m, int middle, int n) {

	int i = m, j = middle + 1, k = m;

	while ((i <= middle) && (j <= n)) {
		if (a[i] <= a[j]) {
			sorted[k] = a[i];
			i++;
		}
		else {
			sorted[k] = a[j];
			j++;
		}
		k++;
	}
	if (i > middle) {
		for (int t = j; t <= n; t++) {
			sorted[k] = a[t];
			k++;
		}
	}
	else {
		for (int t = i; t <= middle; t++) {
			sorted[k] = a[t];
			k++;
		}
	}

	for (int t = m; t <= n; t++) {
		a[t] = sorted[t];
	}

	return;
}
void Merge_Sort(int a[], int m, int n) {

	int middle;

	middle = (m + n) / 2;

	if (m < n) {
		Merge_Sort(a, m, middle);
		Merge_Sort(a, middle + 1, n);
		Merge(a, m, middle, n);
	}

	return;
}
int main(void) {

	scanf("%d", &number);

	for (int x = 0; x < number; x++) {
		scanf("%d", &data[x]);
	}

	Merge_Sort(data, 0, number - 1);

	for (int x = 0; x < number; x++) {
		printf("%d\n", sorted[x]);
	}

	return 0;
}

djm03178 2년 전 0

n=1일 때 틀리게 됩니다.

사실 일반적으로 정렬을 해주는 함수의 역할을 생각해 보면 sorted를 출력하는 게 아니라 data를 출력하는 것이 의미상 더 바람직합니다. sorted는 정렬 과정에서 사용한 임시 배열에 불과하고, 처음부터 원했던 기능은 data 배열 자체가 정렬되는 것이기 때문입니다.

1
1

akdlzhf2008 2년 전 0

와.. 그렇네요..

Merge 함수에서 마지막에 data배열에 정렬된 배열 넣었는데 제가 sorted 배열을 출력을 했더라구요.

data배열 출력하는거로 바꾸니깐 맞았습니다

번외로 추가 질문 좀 드리자면

혹시 n=1 일 때 틀리게 된다는 것을 코드를 보고 아신건가요? 또 sorted로 했을때 1넣으면 0이 나오던데 이건

if ( m < n ) 에 포함되지 못하고 함수가 종료되어서 결국 sorted 에 정렬할 원소가 못들어가서 그런건가요?

djm03178 2년 전 1

같은 이유로 틀린 코드를 몇 번 본 적이 있습니다. 이런 코드들은 공통적으로 n=1일 때 말씀하신 이유로 sorted에 원소가 들어가지 않아서 틀리게 됩니다.

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

문제

문제

출처

ICPC

[C] Merge Sort 어떤 부분 때문에 틀렸는지 좀 봐주세요.

akdlzhf2008 2년 전 0

djm03178 2년 전 0

akdlzhf2008 2년 전 0

djm03178 2년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말