분할

배열을 분할한다는 것은 배열로부터 임의의 수를 가져와(이후 이 수를 피벗이라 부름)

 

피벗보다 작은 모든 수는 피벗의 왼쪽에, 피벗보다 큰 모든 수는 피벗의 오른쪽에 두는 것. 

 

예시)

{0,5,2,1,6,3}의 배열이 있다고 치자. 

3을 피벗으로 하여 3보다 작은 값들을 왼쪽에 높은 값들을 오른쪽에 두면 끝이다.

 

public class PartitionSort {
	public static void main(String[] args) {
		int[] a = { 0, 5, 2, 1, 6, 3 };
		partition(a, 0, a.length - 1);
	}

	private static void partition(int[] a, int left, int right) {
		int pivot_position=right;
		int pivot=a[pivot_position];
		
		right-=1;
		
		while(true) {
			while(a[left]<pivot) {
				left+=1;
			}
			while(a[right]>pivot) {
				right-=1;
			}
			if(left>=right) {
				swap(a,left,pivot_position);
				break;
			}else {
				swap(a,left,right);
			}
		}
		System.out.println(Arrays.toString(a));
	}

	private static void swap(int[]a,int left, int right) {
		int tmp=a[left];
		a[left]=a[right];
		a[right]=tmp;
	}
}

left와 right는 포인터를 의미한다.

 

이 부분을 이해하면 쉽다.

 

책에 예제가 루비로 나와있어 잠깐 당황했는데, 그렇게 어려운 개념이 아니였다.

 

public class PartitionSort {
	public static void main(String[] args) {
		int[] a = { 0, 5, 2, 1, 6, 3 };
		quickSort(a, 0, a.length-1);
		System.out.println(Arrays.toString(a));
	}

	public static int partition(int[] a, int left, int right) {
		int pivot_position = right;
		int pivot = a[pivot_position];

		right -= 1;
		while (true) {
			while (a[left] < pivot) {
				left++;
			}
			while (a[right] > pivot) {
				right--;
				if(right<0) { // 이 부분을 넣어주지 않으면  right가 -1이 되면서 ArrayOutofBoundsExcepction 발생
					break;
				}
			}
			if (left >= right) {
				swap(a, left, pivot_position);
				break;
			} else {
				swap(a, left, right);
			}
		}
		return left;
	}
	public static void quickSort(int[]a,int left, int right) {
		if(right-left<=0) {
			return;
		}
		int pivot_position=partition(a, left, right);
		
		quickSort(a, left, pivot_position-1);
		
		quickSort(a, pivot_position+1, right);
	}
	private static void swap(int[]a,int left, int right) {
		int tmp=a[left];
		a[left]=a[right];
		a[right]=tmp;
	}
}

분할을 응용한 재귀 함수 호출 사용 예제이다.

 

quickSort 함수를 이용해서 

 

기저 조건 설정 : right-left<=0 재귀가 끝난다.

 

첫번째 재귀인 quickSort(a, left, pivot_position-1); 은 

 

배열과, 왼쪽 시작점(index(0)), 오른쪽 시작점(index(3))이 대입된다.

 

3-0=3이 0보다 크므로 기저조건 X

 

pivot_position을 partition함수를 통해 얻는다. 그러면서 partition 함수를 통해 순서가 정렬된다. 

 

이 예제에서는 앞 부분은 정렬이 되어 있기에 이런 과정을 거친다.

 

0 1 2 3 6 5 에서

 

0 1 2 이 부분 처음 qickSort

 

2가 피벗

 

0에 왼쪽 포인터, 1에 오른쪽 포인터

 

0이 2보다 작으면 왼쪽 포인터가 오른쪽으로 한 칸 움직인다. 

 

왼쪽 포인터가 1을 가리키게 된다. 

 

1이 2보다 작기 때문에 왼쪽 포인터가 오른쪽으로 한 칸 움직인다.

 

이때 왼쪽 포인터가 가르키는 값이 피벗과 동일하므로 왼쪽 포인터를 멈춘다. 

 

이제 오른쪽 포인터(1)를 동작시킨다. 

 

1(a[right])은 2(pivot)보다 작기 때문에 while(a[right]>pivot) 이 반복문이 실행되지 않는다.

 

마지막 단계로 피벗(3)과 왼쪽 포인터 값(3)을 교환한다. 

 

같기 때문에 변화는 일어나지 않는다.

 

다시 두번째 quickSort함수가 실행된다. quickSort(a배열,0,pivot_position(2)-1=1)

 

pivot_position=

 

이부분이 반복 

 

왼쪽 포인터 오른쪽 포인터도 0을 가르키면서 시작

 

1번이 피벗

 

0이 1보다 작으니 왼쪽 포인터가 오른쪽으로 한 칸 움직인다.

 

피벗과 동일하므로 피벗과 swap하고 break한다.(변화가 없다.)

 

세번째 quickSort 함수. quickSort(a배열, 0, pivot_position(1)-1=0)

 

기저조건 right-left=<0을 만족하므로 재귀를 빠져나온다. 

 

오른쪽도 마찬가지로 똑같이 이루어 지는데, 6,5 이렇게 되어있는 부분이 5,6이렇게 정렬이 된다.