Quick sort

public class quicksort {
	static int[] a;
	
	public static void main(String[] args) {
		a = new int[]{1,2,4,6,3,7,9,8,10};
		quick_sort(a,0,a.length-1);
		
		for(int i = 0; i < a.length; i++) {
			System.out.print(a[i]);
		}
		
	}

	public static void quick_sort(int[] data, int start, int end) {
		if (start >= end) {
			return;
		}
		int key = start;
		int i = start + 1;
		int j = end;
		int temp;
		
		while(i <= j) {
			while(i <= end && data[i] <= data[key]) {  // 키 값보다 큰 값 만날때 까지 이동 
				i++;
			}
			while(start < j && data[j] >= data[key]) { // 키 값보다 작은 값 만날때 까지 이동 
				j--;
			}
			if( j < i) { // 엇갈리면 키 값 교
				temp = data[j];
				data[j] = data[key];
				data[key] = temp;
			}else {
				temp = data[i];
				data[i] = data[j];
				data[j] = temp;
			}
		}
		
		quick_sort(data, start, j-1);
		quick_sort(data, j+1, end);
		
		
	}

}

맨 처음엔 그냥 외워서 코드 치다보니까 왜 이런지 이해가 되었다...
힝 오랜만에 좀 복잡한거 공부하니 집중도 잘 안되고 이해력도 현저히 떨어졌다.
지금까진 웜업이고.. 천천히 올려봐야겠다.

우선, 재귀를 짤때 먼저 탈출 조건을 만들어야 한다.
탈출 조건은, 1개만 남았을때, 즉 끝점이 피봇과 같아질때 끝내준다.

그리고 시작점은 피봇, 그리고 i,j를 피봇 다음 포인트와 끝점으로 세팅한다.

이제, i 와 j 를 옮겨줄건데, i는 끝 점 보다 넘겨버리거나, 자기자신보다 큰 값을 만날때까지,
그리고 j 는 피봇을 만날때 까지, 그리고 자기 자신보다 작은값을 만날때까지 가게된다.

그리고 이제 i와 j가 엇갈리게되면 피봇값을 j와 교환해준다. 그렇게 되면, 교환된 피봇값을 기준으로 왼쪽은 무조건 피봇값보다 작고 오른쪽은 큰 값이 된다.
그리고 이제 루프를 빠져 나오고 다시 퀵정렬을 j값은 고정이니 그 앞과 그 뒤로 돌려주면 된다.

만약 교차하는게 없을경우는 i의 위치와 j의 위치를 변경한다. 왜냐면 그렇게 해야 큰 값은 뒤로가고 작은 값은 앞으로 오니까. 그리고 이렇게 하는 순간 훗날에 교차하게될때 그 왼쪽값은 무조건 피봇보다 작은값이 된다.