글 읽기 - 수 정렬하기 2 퀵소트 런타임에러 나는 이유 알 수 있을까요?

ook505 7년 전 0

고수님들 도와주시면 정말 감사하겠습니다.ㅠ

버블 정렬로 구현해서 시간 초과가 뜨길래 퀵 소트로 구현했더니 이번에는 런타임 에러가 뜨네요...

동적 할당도 제대로 했는데 어디서 문제가 생긴건지 도와주시면 정말 감사하겠습니다...

#include <stdio.h>
void quickSort(int nums[], int left, int right);
void swap(int *p, int *q);
int main()
{
	int i, n, *nums;
	scanf("%d", &n);
	nums = (int *)malloc((n + 1)* sizeof(int));
	for (i = 0; i < n; i++)
		scanf("%d", &nums[i]);
	quickSort(nums, 0, n - 1);
	for (i = 0; i < n; i++)
		printf("%d\n", nums[i]);
	free(nums);
}
void quickSort(int nums[], int left, int right)
{
	int pivot, i, j;
	i = left;
	j = right + 1;
	pivot = nums[left];
	if (left < right) {
		do {
			do i++; while (nums[i] < pivot);
			do j--; while (nums[j] > pivot);
			if (i < j) swap(&nums[i], &nums[j]);
		} while (i < j);
		swap(&nums[left], &nums[j]);
		quickSort(nums, left, j - 1);
		quickSort(nums, j + 1, right);
	}
}
void swap(int *p, int *q)
{
	int temp = *p;
	*p = *q;
	*q = temp;
}

occidere 7년 전 1

지하철이라 꼼꼼히 읽어보진 못했으나 동적할당 하려면 #include<stdlib.h> 해줘야되지 않나요?

ook505 7년 전 1

음.. #include<stdlib.h> 추가해도 런타임 에러가 뜨네요ㅠ

3587jjh 7년 전 1

정렬해야할 수가 하나일때 해보셨나요?

occidere 7년 전 1

1. 먼저 문제에서 정렬해야되는 수가 n 개이므로 동적할당도 n개만 해줘야 합니다.

-> 8번줄에 n+1을 n으로 고쳐주세요

2. 마지막으로 퀵정렬하며 i와 j를 이동시킬 때, 인덱스 범위를 넘어버리는 경우가 발생합니다.

-> 24, 25번라인의 while문 내에 각각 && i<right와&& j>left를 추가해 주세요.

아래는 해당 부분들을 수정하여 AC받은 코드입니다

#include <stdio.h>
#include <stdlib.h>
void quickSort(int nums[], int left, int right);
void swap(int *p, int *q);
int main()
{
	int i, n, *nums;
	scanf("%d", &n);
	nums = (int *)malloc((n)* sizeof(int));
	for (i = 0; i < n; i++)
		scanf("%d", &nums[i]);
	quickSort(nums, 0, n - 1);
	for (i = 0; i < n; i++)
		printf("%d\n", nums[i]);
	free(nums);
}

void quickSort(int nums[], int left, int right)
{
	int pivot, i, j;
	i = left;
	j = right + 1;
	pivot = nums[left];
	if (left < right) {
		do {
			do i++; while (nums[i] < pivot && i<right);
			do j--; while (nums[j] > pivot && j>left);
			if (i < j) swap(&nums[i], &nums[j]);
		} while (i < j);
		swap(&nums[left], &nums[j]);
		quickSort(nums, left, j - 1);
		quickSort(nums, j + 1, right);
	}
}
void swap(int *p, int *q)
{
	int temp = *p;
	*p = *q;
	*q = temp;
}

ook505 7년 전 1

와.. i와 j가 인덱스의 범위를 벗어날 경우를 생각하지 못했네요..

덕분에 해결했습니다. 정말 감사합니다!(꾸벅)

ook505 7년 전 1

시간 내주셔서 정말 감사합니다.

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

문제

문제

출처

ICPC

수 정렬하기 2 퀵소트 런타임에러 나는 이유 알 수 있을까요?

ook505 7년 전 0

occidere 7년 전 1

ook505 7년 전 1

3587jjh 7년 전 1

occidere 7년 전 1

ook505 7년 전 1

ook505 7년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말