08-중간값-퀵소트.md

중간값 퀵소트

• 피벗값을 맨 앞, 맨 뒤로 설정하는 것에 대한 대안이 바로 '중간값 퀵소트' "Median QuickSort" 이다.

1. front, mid, rear 세 부분을 먼저 소트 해준다.
2. 만약 요소가 4개 이상으로 남아있다면, 기존의 퀵소트와 같은 방식으로 파티션을 해준다.
3. 이 후, 피벗값의 자리를 기준으로 피벗값 앞, 피벗값 뒤를 다시 퀵소트 알고리즘을 호출해준다.

1. pivot 값을 rear - 1 로 옮겨주는 이유는, 파티션 루프를 통해서 앞쪽엔 피벗보다 작은값, 뒷쪽엔 피벗보다 큰 값으로 나누어주는 것이므로, 가운데에 위치한 우리의 pivot을 rear-1로 옮겨주고 진행한다. 따라서 파티션은 front +1, rear -2 부터 시작된다. (front, mid, rear는 정렬되었으므로)

2. 마지막에 파티션을 다하고 피벗과 i를 바꾸는 이유 = i는 현재 pivot보다 큰 값을 가리키고 있다. 피벗은 rear-1에 위치해 있다. 그렇기 때문에 i와 pivot의 위치를 스왑해주어야만, 피벗값이 올바른 자리에 들어가게 된다. (피벗의 오른쪽을 피벗보다 큰 값들로 위치시켜야 하므로)

public class QuickSort {

	private static void swap(int arr[], int a, int b) { //스왑함수
		int tmp=arr[a];
		arr[a]=arr[b];
		arr[b]=tmp;
	}

	private static void sortThree(int arr[], int front, int mid, int rear) {
    // 3개의 요소를 소트하는 함수
		if(arr[front]>arr[mid]) swap(arr,front,mid);
		if(arr[mid]>arr[rear]) swap(arr,mid,rear);
		if(arr[front]>arr[mid]) swap(arr,front,mid);
	}

	public static void MedianQuickSort(int arr[], int front, int rear) {
    //퀵소트 실행함수
		int mid = (front+rear)/2;
		sortThree(arr,front,mid,rear);
		int i, j, pivot;

		if(rear-front>2) { //요소가 3개 이하라면, 위의 sortThree에서 이미 소트가 완료
			pivot=arr[mid];
			swap(arr,mid,rear-1);
			i=front;
			j=rear-1;
			while(true) {
				while(arr[++i]< pivot && i<rear);
				while(arr[--j]>pivot && j>front);
				if(i>=j) break;
				swap(arr,i,j);
			}
			swap(arr,i,rear-1);
			MedianQuickSort(arr, front, i-1);
			MedianQuickSort(arr,i+1,rear);
		}
	}
}