JustZ
97
2020-05-01 00:51:17
1
250

자바로 퀵 정렬을 만들었는데 무한루프가 되었습니다.



package Sort;

import java.util.Arrays;

public class QuickSort {

	public static void main(String[] args) {
		long starTime = System.nanoTime();
		
		int[] arr = {5,10,3,8,1,6,4,7,2,9};
		quickSort(arr, 0, arr.length-1); // 퀵 소트를 실행해보자!
		
		System.out.println(Arrays.toString(arr));
		
		long finishTime = System.nanoTime();
		System.out.println("Time: " +(finishTime-starTime));

	}
	static void quickSort(int[] data, int start, int end) {
		int pivot = start;
		int left = start+1; // 키값 오른쪽부터 큰값 확인하는 인덱스
		int right = end; // 마지막부터 키값보다 작은값 확인하는 인덱스
		int temp=0; // 스왑하기 위한 빈 변수
		
		while(!(left>right)) {
			while(!(data[left]>data[pivot]||left<=end)) left++; // 키값보다 큰 수를 만나면 멈춤
			while(!(data[right]<data[pivot]||right>=start)) right--; // 키값보다 작은 수를 만나면 멈춤
			if(left>right) { // 서로 엇갈린 경우 스왑
				temp = data[right];
				data[right] = data[pivot];
				data[pivot] = temp;
			}
			else { // left와 right 끼리 서로 바꿈
				temp = data[right];
				data[right] = data[left];
				data[left] = temp;
			}
		}
		
		quickSort(data, start, right-1); // 피벗보다 작은 수들의 정렬
		quickSort(data, right+1, end); // 피벗보다 큰 수들의 정렬
	}
}

퀵 정렬에 대해서 공부하고 만들어 보았는데 무한루프에 빠졌습니다.

30분동안 고민을 해보았지만 어떤 부분에서 잘못된건지 모르겠습니다...

0
0
  • 답변 1

  • 봄을찾아서
    237
    2020-05-01 09:54:54

    재귀함수는 기본적으로 탈출 조건이 있어야 합니다.

    quikSort 함수에서 start와 end 값에 따라 함수가 종료(return) 될 수 있도록 해줘야 할 것 같아요.

    안그러면 재귀함수가 무한히 호출될 것 같습니다.

    1
  • 로그인을 하시면 답변을 등록할 수 있습니다.