글 읽기 - 퀵솔트 질문입니다.

whitour 7년 전 0

오름차순 정렬을 퀵솔트로 구현해보았는데 정답이 아니라고 떠서 이렇게 질문드립니다.

어디에서 문제가 있을까요? 첨부합니다.

import java.util.Scanner;

public class Main {
	
	public static void main(String[] args){
		Scanner sc=new Scanner(System.in);
		int x = sc.nextInt();
		int[] intArray = new int[x];
		for(int i=0; i<x; i++){
			intArray[i] = sc.nextInt();
		}
		Main main = new Main();
		main.quickSort(intArray, 0, intArray.length-1);
		
		for(int i=0; i<intArray.length; i++){
			System.out.println(intArray[i]);
		}	
	}
	
	public void quickSort(int[] intArray, int left, int right){
		int pivot = intArray[left];
		int l_hold = left;
		int r_hold = right;
		
		while(true){
			while(intArray[left]<pivot && left<right){
				left++;
			}
			while(intArray[right]>pivot && left<right){
				right--;
			}
			if(left != right){
				int temp = intArray[left];
				intArray[left] = intArray[right];
				intArray[right] = temp;
				left++;
				continue;
			}else{
				int samePoint = left;
				int pivotPoint = l_hold;
				if(pivot>intArray[samePoint]){
					int temp = pivot;
					intArray[pivotPoint] = intArray[samePoint];
					intArray[samePoint] = temp;
				}
				if(samePoint>l_hold){
					quickSort(intArray, l_hold, samePoint-1);
				}
				if(samePoint<r_hold){
					quickSort(intArray, samePoint+1, r_hold);
				}
				break;
			}
		}
	}
}

whitour 7년 전 0

자답입니다. 문제는 41라인에 조건이 일치하지 않을 경우 피벗의 위치를 변경해주지 않고 계속 진행해나가면서 일어난 문제군요.

수정한 코드입니다. 혹시 더 나은 해결책이 있다면 부탁드립니다 ㅠ 효율성 측면에서요

if(pivot<intArray[samePoint]) samePoint--;
int temp = pivot;
intArray[pivotPoint] = intArray[samePoint];
intArray[samePoint] = temp;

if(samePoint>l_hold){
quickSort(intArray, l_hold, samePoint-1);
}
if(samePoint<r_hold){
quickSort(intArray, samePoint+1, r_hold);
}
break;
}
}
}
}

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

문제

문제

출처

ICPC

퀵솔트 질문입니다.

whitour 7년 전 0

whitour 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말