[코딩 문제] - 6/15 ~ 6/17 퀵 정렬

퀵 정렬(week02 과제)

[5 1 9 10 4 2 7 3 6 8]
↑↑                     ↑
 p L                      H

pivot(피벳, 피봇, 기준)

p에 대하여 L, H가 올바른지 확인
5보다 작은 애들만 LOW
5보다 큰 애들만 HIGH

[5 1 9 10 4 2 7 3 6 8]
↑   ↑            ↑
 p    L             H

L먼저 체크 : p보다 큰 수를 만나면 스톱!
H      체크 : p보다 작은 수를 만나면 정지!
L <-> H 교환 : 교환알고리즘 사용
  >>많이 틀리는 것
  >> 교환의 대상은 배열임에 유의!
[5 1 3 10 4 2 7 9 6 8]
↑   ↑            ↑
 p    L             H

[5 1 3 10 4 2 7 9 6 8]
↑       ↑   ↑
 p        L    H

[5 1 3 2 4 10 7 9 6 8]
↑         ↑↑
 p          H L
         (교차발생)
루프 시행중에 교차(CROSS)발생하면
       >> STOP 멈춰라!

[4 1 3 2 5 10 7 9 6 8]
↑         ↑↑
 p          H L
pivot과 H를 교환 
     >> 1회전 정렬

q(배열, 0, 9){
       q(배열, 0, H-1);
       q(배열, L, 9);
}

-------------강사님 코딩( 디버깅표 짜면 다시 갱신 )

package test;
public class Test02 {
	static void quick_sort(int[] data, int start, int end) {
		if(start >= end) { // 정렬할 배열요소가 없다면
			return; // 반환값을 나를 호출한 위치로 전달
			// 함수 즉시 종료
		}
		int pivot=data[start];
		int L = start + 1;
		int H = end;
		while(true) {
			while(pivot>data[L]) {
				if(L==end) { // L이 끝까지 도달했다면
					break; // 그만해라!
				}
				L++; // ※ index 범위를 ++, -- 때에는 Exception에 유의하자!
				// 피벗의 기준이 (우연찮게) 10이면 나갈 수도 있기 때문에
			}
			while(pivot<data[H]) {
				if(H==start) {
					break;
				}
				H--;
			}
			System.out.println("L = " + L + " H = " + H);
			// 교차되었어? 종료조건
			if(L >= H) {
				int tmp = data[start]; // 배열을 교환한다!
				data[start] = data[H];
				data[H] = tmp;
				break;
			}
			int tmp = data[L];
			data[L] = data[H];
			data[H] = tmp;
		}
		quick_sort(data,start,H-1);
		quick_sort(data,H+1, end);
	}
	public static void main(String[] args) {
		// 재귀 함수??
		// 로직을 코드로 옮길 수 있나???
		int[] data = {5,1,9,10,4,2,7,3,6,8};
		for(int i = 0; i < data.length; i++) {
			System.out.print(data[i] + " ");
		}
		System.out.println();
		quick_sort(data,0,data.length-1);
		// 메서드 시그니처 : 함수 3요소 -> input, output, 기능
		// int[] x1, intx2  |   xxx(void)   |   퀵 정렬
		for(int i = 0; i < data.length; i++) {
			System.out.print(data[i] + " ");
		}
		System.out.println();
	}
}