글 읽기 - 1920 런타임 에러;;

donghy9508 7년 전 0

시간초과나서 버블소트에서 퀵소트로 정렬 바꿨는데 런타임에러가 나왔어요;;

도움 부

#include<stdio.h>
void quicksort(int*, int, int);//퀵소트 (배열, 왼쪽인덱스,오른쪽인덱스)
int binarysearch(int*, int, int);//이진탐색(검색배열,찾는수,크기)
int main(void){
	int n, m, num = 0, a[100000];
	scanf("%d", &n);
	for (int i = 0; i < n; i++){
		scanf("%d", &a[i]);
	}

	quicksort(a, 0, n - 1);
	scanf("%d", &m);
	for (int i = 0; i < m; i++)
	{
		scanf("%d", num);
		if (binarysearch(a, num, n) == -1)
			printf("%d\n", 0);
		else
			printf("%d\n", 1);
	}

}
void quicksort(int*arr, int l, int r){
	int i = l, j = r, temp;
	int pivot = arr[(l + r) / 2];
	while (i <= j)
	{
		while (arr[i] < pivot)
			i++;
		while (arr[j]>pivot)
			j--;
		if (i <= j){
			temp = arr[i];
			arr[i] = arr[j];
			arr[j] = temp;
			i++, j--;
		}
	}
	if (l < j)
		quicksort(arr, l, j);
	if (i < r)
		quicksort(arr, i, r);
}
int binarysearch(int* arr, int find, int n){
	int left = 0;
	int right = n - 1;
	int mid;
	while (left <= right){
		mid = (left + right) / 2;
		if (arr[mid] > find)
			right = mid - 1;
		else if (find > arr[mid])
			left = mid + 1;
		else
			return mid;
	}

	return -1;
}

lohaswinner 7년 전 0

stdlib.h 에 qsort 와 bsearch 가 있고, C++ algorithm 에 sort 와 binary_search 가 있는데 굳이 직접 작성해야 하는 이유를 모르겠군요.

작성하신 quicksort 가 call stack 부족상황을 초래할지도 모르므로 직접 작성하신다면 merge sort 나 heap sort 로 구현해보시는게 어떨까 싶네요.

이분검색도 정확하게 작성한다는게 의외로 쉽지 않습니다.

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

문제

문제

출처

ICPC

1920 런타임 에러;;

donghy9508 7년 전 0

lohaswinner 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말