글 읽기 - 같은 while문의 성능 차이에 대해 질문드립니다.

aaadddggg 7년 전 0

1번 코드

while(numbers[left] < numbers[pivot] && left < end)++left;
while(numbers[right] > numbers[pivot] && right > start)--right;

2번 코드

while(numbers[++left] < numbers[pivot] && left < end);
while(numbers[--right] > numbers[pivot] && right > start);

[질문]

퀵정렬 구현 중 left와 right의 인덱스를 늘이고 줄이는 반복문을 1번코드처럼 작성하여 시간초과가 났습니다.

그러던 중 2번코드처럼 바꾸었더니 정답처리되었습니다.

아무리 생각해도 1번과 2번이 성능차이가 그리 크지 않을 것 같은데 3번이나 반복하였으나 1번은 뚝심있게 시간초과가 뜨고(...) 2번은 정답처리 되는 것을 보니 단순한 운은 아닌 것 같습니다.

왜 이런지 아시는 고수님들의 답변 기다리고 있겠습니다~!

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {
	private static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
	private static BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
	
	private static int[] numbers;
	public static void main(String[] args)throws IOException{
		int size = Integer.parseInt(reader.readLine());
		numbers = new int[size];
		for(int i = 0; i < size; i++)numbers[i] = Integer.parseInt(reader.readLine());
		
		dp(0, size - 1);
		
		for(int i = 0; i < size; i++)writer.write(String.valueOf(numbers[i]) + "\n");
		writer.flush();
	}
	private static void dp(int start, int end){
		if(end == start)return;
		
		int mid = (start + end) / 2;
		threeSort(start, mid, end);
		
		if(end - start < 3)return; //3개 이하의 부분배열은 threeSort()로 완전히 정렬됨
		
		int pivot = end - 1;
		SWAP(mid, pivot); 				 //numbers[mid]를 end - 1의 위치로 이동시키고, 피벗으로 함.
		int pivotValue = numbers[pivot]; //numbers[end]는 이미 numbers[mid]를 피벗으로 삼으면 오른쪽에 있으므로 고려할 필요 없음.
		
		int left = start, right = pivot;
				
		while(true){
			//while(numbers[left] < pivotValue && left < pivot)++left;			
			//while(numbers[right] > pivotValue && right > start)--right;
			while(numbers[++left] < numbers[pivot] && left < end);
			while(numbers[--right] > numbers[pivot] && right > start);
			
			if(left >= right)break;
			SWAP(left, right);
		}
		SWAP(left, pivot);
		
		dp(start, left - 1);
		dp(left + 1, end);
	}
	private static void SWAP(int index1, int index2){
		int t = numbers[index1];
		numbers[index1] = numbers[index2];
		numbers[index2] = t;
	}
	private static void threeSort(int index1, int index2, int index3){
		if(numbers[index1] > numbers[index2])SWAP(index1, index2);
		if(numbers[index2] > numbers[index3])SWAP(index2, index3);
		if(numbers[index1] > numbers[index2])SWAP(index1, index2);
	}
}

sgchoi5 7년 전 1

적어도 퀵정렬 코드 전체는 있어야 고수님들도 봐주실 수 있을 듯 한데.. ^^;;

aaadddggg 7년 전 0

코드 업로드하였습니다.

코드상의 39~40줄을 주석처리하고 37~38줄을 살린다음 left = start + 1, right = pivot - 1로 테스트하면 시간초과가 뜨네요 ㅠ

allkanet72 7년 전 0

while(numbers[left] < numbers[pivot] && left < end)++left; = //while(numbers[left] < pivotValue && left < pivot)++left;

while(numbers[right] > numbers[pivot] && right > start)--right; = //while(numbers[right] > pivotValue && right > start)--right;

위 설명하신 코드랑 아래 코드랑 시간 초과 난다는 부분이 이거 맞나요? 1번 이랑 주석 처리한 부분이 달라서요.

allkanet72 7년 전 1

주석 풀고 컴파일하니 아예 무한루프 도네요. 로직이 잘못된듯

10
39
33
20
11
3
40
33
40
55
60

aaadddggg 7년 전 0

감사합니다~! 무한루프 힌트를 주셔서 혹시나 해서 같은 숫자 5개를 넣어봤는데 무한루프에 돌더라고요.

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

문제

문제

출처

ICPC

같은 while문의 성능 차이에 대해 질문드립니다.

aaadddggg 7년 전 0

sgchoi5 7년 전 1

aaadddggg 7년 전 0

allkanet72 7년 전 0

allkanet72 7년 전 1

aaadddggg 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말