aaadddggg   2년 전

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번은 정답처리 되는 것을 보니 단순한 운은 아닌 것 같습니다.

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

sgchoi5   2년 전

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

aaadddggg   2년 전

코드 업로드하였습니다.

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

allkanet72   2년 전

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   2년 전

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

10
39
33
20
11
3
40
33
40
55
60


aaadddggg   2년 전

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

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