자바 퀵정렬 코딩중에 잘 모르는 부분이 있어서 질문드립니다. 스스로 많이 생각했씁니다

bke2003의 이미지

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값이 같은 값을 가지고 있는데 왜 서로 결과값 차이가 나는지 모르겠습니다.

진짜 소스가 난잡하고 기본적인 알고리즘이긴 하지만

스스로 정말 많이 고민했습니다.. 간단하지만..ㅠㅠ

퀵정렬 원리만 보고 스스로 생각하면서 작성하는게 목표여서 최대한 스스로 생각한대로 작성햿는데

하도 안되서 다른 코드들이랑 비교해보면 구조는 비슷한거같은데 제 코드는 어디선가 이상한지 계속 다른값이 나옵니다..

자그만한 깨우침이라도 주세요... 부탁드립니다 ㅠㅠ

익명 사용자의 이미지


얼핏 봤을때 로직에는 문제가 없는 것 같은데...싶다가 본것이
upsort를 연달아 재귀 호출 하는 부분에서요, 윗 부분의 upsort가 실행될때 클래스 속성으로 정의한 right 값이 변하고,
그 변한 right 값이 다음 upsort 문에서 사용 됩니다. 이 문제인듯 싶네요...^^

cwon의 이미지

아악, 그리고 참고로 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

이런 식이네요~ 참고하세염.ㅋㅋㅋ

댓글 달기

Filtered HTML

  • 텍스트에 BBCode 태그를 사용할 수 있습니다. URL은 자동으로 링크 됩니다.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>
  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.

BBCode

  • 텍스트에 BBCode 태그를 사용할 수 있습니다. URL은 자동으로 링크 됩니다.
  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param>
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.

Textile

  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • You can use Textile markup to format text.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>

Markdown

  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • Quick Tips:
    • Two or more spaces at a line's end = Line break
    • Double returns = Paragraph
    • *Single asterisks* or _single underscores_ = Emphasis
    • **Double** or __double__ = Strong
    • This is [a link](http://the.link.example.com "The optional title text")
    For complete details on the Markdown syntax, see the Markdown documentation and Markdown Extra documentation for tables, footnotes, and more.
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>

Plain text

  • HTML 태그를 사용할 수 없습니다.
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.
  • 줄과 단락은 자동으로 분리됩니다.
댓글 첨부 파일
이 댓글에 이미지나 파일을 업로드 합니다.
파일 크기는 8 MB보다 작아야 합니다.
허용할 파일 형식: txt pdf doc xls gif jpg jpeg mp3 png rar zip.
CAPTCHA
이것은 자동으로 스팸을 올리는 것을 막기 위해서 제공됩니다.