글 읽기 - 퀵소트와 병합정렬

choyj1127 1년 전 0

밑코드에서 주석처리한 퀵소트를 사용했다가 틀렸습니다가 나왔습니다

이 후 병합정렬을 사용하여 제출하니 맞았다고 나왔는데

퀵소트가 최악의 경우 시간복잡도가 n^2라고는 알고있긴했는데 시간초과도 아니고 틀렸습니다가 뜬건 다른 이유가 있는건가요? 궁금하여 질문합니다

#include <stdio.h>
#include <stdlib.h>
int n[100000];
int m[100000];
int N, M;
//
//int compare(const void* a, const void* b) {
//	return *(int*)a - *(int*)b;
//}
void mergeTwoArea(int arr[], int left, int mid, int right) {
	int fIdx = left;
	int rIdx = mid + 1;
	int* sortArr = (int*)malloc(sizeof(int) * N);
	int sIdx = left;
	while (fIdx <= mid && rIdx <= right) {
		if (arr[fIdx] <= arr[rIdx]) sortArr[sIdx++] = arr[fIdx++];
		else sortArr[sIdx++] = arr[rIdx++];
	}
	while (fIdx <= mid) sortArr[sIdx++] = arr[fIdx++];
	while (rIdx <= right) sortArr[sIdx++] = arr[rIdx++];

	for (int i = left; i <= right; i++) arr[i] = sortArr[i];
	free(sortArr);
}

void mergesort(int arr[], int left, int right) {
	if (left < right) {
		int mid = (left + right) / 2;
		mergesort(arr, left, mid);
		mergesort(arr, mid + 1, right);
		mergeTwoArea(arr, left, mid, right);
	}
}
int binarysearch(int start, int end, int target) {
	while (start <= end) {
		int mid = (start + end) / 2;
		if (target == n[mid]) return 1;
		else if (target < n[mid]) end = mid - 1;
		else start = mid + 1;
	}
	return 0;
}
int main() {
	scanf_s("%d", &N);
	for (int i = 0; i < N; i++)
		scanf_s("%d", &n[i]);

//	qsort(n, N, sizeof(int), compare);
	mergesort(n, 0, N - 1);

	scanf_s("%d", &M);
	for (int i = 0; i < M; i++) {
		scanf_s("%d", &m[i]);
		printf("%d\n", binarysearch(0, N - 1, m[i]));
	}

	return 0;
}

djm03178 1년 전 1

qsort는 퀵소트가 아닙니다. 이 함수를 썼을 때 틀린 건 compare 함수가 틀렸기 때문입니다. 주어지는 정수의 범위가 커서 a - b가 int 범위를 벗어날 수 있습니다.

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

문제

문제

출처

ICPC

퀵소트와 병합정렬

choyj1127 1년 전 0

djm03178 1년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말