[자료구조 복습 11] Median of Three Quick Sort중간값 퀵소트

중간값 퀵소트

(중간값 퀵소트에 대한 내용은 https://blog.naver.com/occidere/220870294816 를 참고했음을 밝힌다.

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

중간값 퀵소트의 원리는 일단 다음과 같다.

 

 

1. front, mid, rear 세 부분을 먼저 소트 해준다.

2. 만약 요소가 4개 이상으로 남아있다면, 기존의 퀵소트와 같은 방식으로 파티션을 해준다.

   -> 이 후, 피벗값의 자리를 기준으로  피벗값 앞, 피벗값 뒤를 다시 퀵소트 알고리즘을 호출해준다.

 

헷갈리는 내용이 많으니 아래 그림과 정리를 보면서 이해해보자.

 

 

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);
		}
	}
}