퀵 정렬(Quick Sort)

 

- 퀵 정렬

 

public class QuicSort {
	public static void quickSort(int[] arr, int left, int right) {
	    int i, j, pivot, tmp;
	    if (left < right) {
	        i = left;   j = right;
	        pivot = arr[(left+right)/2]; // arr에 중간 index 값을 찾는다.
	        System.out.println("기준 값 : "+ pivot);
	        //분할 과정
	        while (i < j) {
	        	// i : pivot 보다 큰 값의 index
	        	// j : pivot 보다 작은 값의 index
	            while (arr[j] > pivot) j--; // pivot 보다 작은값의 index을 찾는다.
	            // 이 부분에서 arr[j-1]에 접근해서 익셉션 발생가능함.
	            while (i < j && arr[i] < pivot) i++; // pivot 보다 큰값의 index을 찾는다.
	            System.out.print(i + "index : " + arr[i] + " , ");
	            System.out.println(j + " : " + arr[j]);
	            tmp = arr[i]; // pivot 보다 큰값
	            arr[i] = arr[j]; // pivot 보다 큰 값과 작은 값의 위치를 바꾼다. 왼쪽 오른쪽 정렬
	            arr[j] = tmp; // 
	        }
	        System.out.println();
	        //정렬 과정
	        System.out.println("a : "+ left + "~" + (i - 1));
	        System.out.println("b : "+ (i + 1) + "~" + right);
	        quickSort(arr, left, i - 1);
	        quickSort(arr, i + 1, right);
	    }
	}
	
	public static void main(String[] args) {
		int[] arr = {1 ,4, 2, 8, 10, 7, 3, 9, 5, 6};
		quickSort(arr, 0, arr.length-1);
		System.out.println(Arrays.toString(arr));
	}
}

결과

기준 값 : 10
4index : 10 , 9 : 6
9index : 10 , 9 : 10

작은값들 검색 범위 : 0~8
큰값들 검색 범위 : 10~9
기준 값 : 6
3index : 8 , 8 : 5
4index : 6 , 6 : 3
5index : 7 , 6 : 6
5index : 6 , 5 : 6

작은값들 검색 범위 : 0~4
큰값들 검색 범위 : 6~8
기준 값 : 2
1index : 4 , 2 : 2
1index : 2 , 1 : 2

작은값들 검색 범위 : 0~0
큰값들 검색 범위 : 2~4
기준 값 : 5
3index : 5 , 4 : 3
4index : 5 , 4 : 5

작은값들 검색 범위 : 2~3
큰값들 검색 범위 : 5~4
기준 값 : 4
2index : 4 , 3 : 3
3index : 4 , 3 : 4

작은값들 검색 범위 : 2~2
큰값들 검색 범위 : 4~3
기준 값 : 9
7index : 9 , 8 : 8
8index : 9 , 8 : 9

작은값들 검색 범위 : 6~7
큰값들 검색 범위 : 9~8
기준 값 : 7
6index : 7 , 6 : 7

작은값들 검색 범위 : 6~5
큰값들 검색 범위 : 7~7
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]