자바 퀵정렬 코딩중에 잘 모르는 부분이 있어서 질문드립니다. 스스로 많이 생각했씁니다
글쓴이: bke2003 / 작성시간: 일, 2016/05/22 - 5:10오후
public class Sort implements ISort { private int pivot; // 피벗 private int left; //배열의 왼쪽 private int right; //배열의 오른쪽 private int temp; //배열의 값들을 바꿀때 사용하는 속성 @Override public void upsort(int[] arr, int i, int j) {//upsort시작 if(i < j){ pivot = j; //pivot 값을 배열의 맨끝으로 지정 left = i; //left의 값 지정 >> 배열의 맨 왼쪽 right = pivot-1; //right의 값 지정 >> 배열의 맨 오른쪽(피벗을 제외한) while (left < right){//while문 시작 while (arr[left] < arr[pivot]) left++; while (arr[right] > arr[pivot] && left < right) right--; if(arr[left] > arr[right]){ temp = arr[left]; arr[left] = arr[right]; arr[right] = temp; } }//while문 끝 temp = arr[pivot]; arr[pivot] = arr[right]; arr[right] = temp; for (int k =0; k < arr.length; k++) System.out.println(arr[k]); System.out.println("==============="); upsort(arr, i, right-1); upsort(arr, right+1, j); } }//upsort끝
이런 식으로 작성했습니다
진짜 스스로 엄청 생각했었는데 도저히 원하는 값이 나오질 않습니다
다른 소스코드들은 피벗이 열 가운데로 지정하던데 저는 처음부터 맨 오른쪽으로 지정하고 싶어서 그렇게 했습니다.
종이에 써가면서 쭉 해봣는데
피벗값이랑 right값이랑 바뀌는 지점
즉 left랑 right의 위치가 곂치거나 교차되는 지점에서 피벗이랑 RIGHT값이랑 바꿧는데
이것도 다른 코드들은 LEFT값이랑 바꾸던데
LEFT랑 바꾸는거와 RIGHT와 바꾸는거랑 차이가 있는지 잘 모르겠는데 결과값은 달라집니다.
제가 어느부분을 놓치고 있기에 그런가요?
그리고 가장 문제는 저 밑에있는 재귀부분인데
저 부분에서 엉켜서 잘 안되는거 같습니다.
누구는 재귀부분에 제가한 right 대신 left로 하던데
손으로 쓰면서 내려가다 보면 저부분에서는
left 값과 right값이 같은 값을 가지고 있는데 왜 서로 결과값 차이가 나는지 모르겠습니다.
진짜 소스가 난잡하고 기본적인 알고리즘이긴 하지만
스스로 정말 많이 고민했습니다.. 간단하지만..ㅠㅠ
퀵정렬 원리만 보고 스스로 생각하면서 작성하는게 목표여서 최대한 스스로 생각한대로 작성햿는데
하도 안되서 다른 코드들이랑 비교해보면 구조는 비슷한거같은데 제 코드는 어디선가 이상한지 계속 다른값이 나옵니다..
자그만한 깨우침이라도 주세요... 부탁드립니다 ㅠㅠ
Forums:
아!
얼핏 봤을때 로직에는 문제가 없는 것 같은데...싶다가 본것이
upsort를 연달아 재귀 호출 하는 부분에서요, 윗 부분의 upsort가 실행될때 클래스 속성으로 정의한 right 값이 변하고,
그 변한 right 값이 다음 upsort 문에서 사용 됩니다. 이 문제인듯 싶네요...^^
추가로(~ 로긴을 안하고 익명으로 썼어요.ㅜㅜ)
아악, 그리고 참고로 upsort 호출 값은 로직에도 문제가 있나봐요,
upsort call with 0 6
upsort call with 8 9
upsort call with 0 1
upsort call with 3 6
upsort call with 0 -1
upsort call with 1 1
upsort call with 3 2
upsort call with 4 6
upsort call with 4 3
upsort call with 5 6
upsort call with 5 4
upsort call with 6 6
upsort call with 8 7
upsort call with 9 9
이런 식이네요~ 참고하세염.ㅋㅋㅋ
댓글 달기