[Algorithm]퀵 정렬(Quick Sort)

퀵 정렬은 합병정렬과 같이 분할-정복-합병의 순서대로 동작하는데, 분할에서 다른 점이 있다. 합병정렬은 N개의 배열을 N/2로 분할 하였다면, 퀵 정렬은 pivot이라는 기준점으로 분할을 한다.

위 그림과 같이 왼쪽은 pivot보다 작은수 오른쪽은 큰 수로 배열 요소의 위치를 지정한다.

Recursive로 분할을 반복하고 partiton함수를 통해 pivot의 위치를 반환받는다. 

partition함수의 동작 순서를 보자. 배열 마지막 15가 pivot으로 정하고 i는 pivot보다 작은 수들의 기준, j는 반복문을 돌릴 변수이다.

1) j가 증가함에 따라 pivot인 15와 비교한다.
2) Arr[ j ] > 15 이면 j++. 아무일도 일어나지 않는다.
2-1) Arr[ j ] <= 15 이면 i++ 하고 Arr[ i ]와 Arr[ j ]를 바꾼다. 다시 j++
3) j가 pivot인 15의 앞 요소까지 오게 되면, i는 현재 15보다 작은 마지막 배열 요소를 가리키고 있다. Arr[ i+1 ] 과 pivot의 자기를 바꾼다.

 설명의 코드는 위와 같다. X는 pivot이고 j는 for문으로 돌린다.


code]

package test;
	public class quickSort {
	public static void main(String[] args) {
	int data[] = {1,3,5,2,8,7,4,9,6,10};
	quickSort(data, 0, data.length-1);
	for(int c : data)
	System.out.print(c+" ");
	}
	public static void quickSort(int data[], int start, int end) {
	if(start < end) {
	int pivotIdx = getPivot(data, start, end);
	/*
	for(int c : data)
	System.out.print(c+" ");
	System.out.println(" "+pivotIdx);
	*/
	quickSort(data, start, pivotIdx-1);
	quickSort(data, pivotIdx + 1, end);
	}
	}
	public static int getPivot(int data[], int start, int end) {
	int i = start-1;
	int pivot = data[end];
	for(int j=start; j<=end-1; j++) {
	if(data[j] <= pivot) {
	int temp = data[++i];
	data[i] = data[j];
	data[j] = temp;
	}
	}
	int temp = data[i + 1];
	data[i + 1] = data[end];
	data[end] = temp;
	return i + 1;
	}
	}