Quick Sort (퀵 정렬)

퀵정렬은 임의의 한 요소(pivot이라 칭함)를 정한 뒤, pivot의 왼쪽에는 pivot보다 작은 것들만, 오른쪽에는 pivot보다 큰 것들만 오게 만드는 Divide & Conquer 알고리즘이다.

Quick Sort 내부에서 divide, 즉 partition하는 과정에 있어 크게 두 가지 접근법이 있다.

1) Hoare's Partition Scheme

2) Lomuto's Partition Scheme

먼저 Hoare's Partition Scheme에 대해 살펴보자.

전체 과정을 정리해 보면 다음과 같다. 특히 Partition 과정을 집중적으로 보도록 하자,

1. 배열의 첫 인덱스를 start로, 길이를 end로 하여 quickSort()를 호출한다. end는 배열의 마지막 index가 아닌 배열의 길이임에 주의하자.

2. quickSort() 내부에서 partition()을 수행하여 pivotIndex를 구한다.

   ㄴ < Partition > 

첫번째 요소를 pivot으로 저장한다.

맨 왼쪽 index를 i, 맨 오른쪽 index를 j에 할당한다.

i가 j보다 작은 동안 반복한다:

pivot보다 작은 값이 나올 때까지 j를 감소시킨다.

i < j 이면, j에 위치한 값을 i에 넣는다.

pivot보다 큰 값이 나올 때까지 i를 증가시킨다.

i < j 이면, i에 위치한 값을 j에 넣는다.

j에 pivot을 삽입하고, j를 리턴한다. (j가 곧 pivotIndex)

          

3. pivotIndex의 좌측과 우측 부분 배열에 대해 재귀적으로 quickSort()를 호출한다.

   (단, start와 end가 바로 옆에 붙어 있을 경우에는 quickSort에서 아무 것도 하지 않는다)

	public class QuickSortHoare {
	/** Hoare's partition scheme **/
	public static void quickSort(int[] input, int start, int end) {
	if (end - start < 2) { // 요소가 1개이면 그냥 return
	return;
	}
	// partition: pivot보다 작은 요소들은 모두 왼쪽으로, 큰 요소들은 모두 오른쪽으로 이동
	// pivot의 최종 위치를 반환함
	int pivotIndex = partition(input, start, end);
	quickSort(input, start, pivotIndex); // 'end' 매개변수는 실제 마지막 인덱스보다 1이 커야 한다. (pivotIndex)
	quickSort(input, pivotIndex + 1, end);
	}
	public static int partition(int[] input, int start, int end) {
	// This is using the first element as the pivot
	int pivot = input[start]; // 첫번째 요소를 pivot으로 정함 (pivot 정하는 방법은 여러가지가 있다)
	int i = start;
	int j = end;
	while (i < j) {
	// NOTE: empty loop body (pivot보다 작은 요소가 나올 때까지 j를 감소시킴. 단 i < j인 동안에만)
	while (i < j && input[--j] >= pivot);
	if (i < j)
	input[i] = input[j]; // 현재 j에 있는 값을 i의 위치에 할당
	// NOTE: empty loop body (pivot보다 큰 요소가 나올 때까지 i를 증가시킴. 단 i < j인 동안에만)
	while (i < j && input[++i] <= pivot);
	if (i < j)
	input[j] = input[i]; // 현재 i에 있는 값을 j의 위치에 할당
	}
	input[j] = pivot;
	return j; // pivot의 위치 반환
	}
	public static void main(String[] args) {
	int[] intArray = {20, 35, -15, 7, 55, 1, -22};
	quickSort(intArray, 0, intArray.length);
	for (int num : intArray) {
	System.out.print(num + " ");
	}
	}
	}

view raw QuickSort.java hosted with ❤ by GitHub

• j와 i를 왔다 갔다하면서 서로 할당하므로, 기존 배열에 데이터를 덮어 쓰더라도 결과적으로 손실이 없다.
• 주의) 가장 왼쪽 요소를 pivot으로 하고 저장한 다음 반복을 시작하므로, 반드시 오른쪽(j)부터 비교를 시작해야만 데이터를 잃지 않는다.
• partition: 어떤 원칙에 의해 pivot을 정하고, pivot의 왼쪽에는 pivot보다 작은 수만, 오른쪽에는 pivot보다 큰 수만 오도록 위치시킨다.
  (pivot 고르는 방법은 자유롭게 정해도 되지만, 여기서는 가장 왼쪽 요소로 한다.)
• partition을 수행한 후 왼쪽과 오른쪽 배열에 대해 각각 quickSort를 수행 => recursive; 즉 모든 요소가 pivot이 됨.
• partition의 마지막 부분에서 'j'에 pivot값을 넣는데, 해당 위치는 모든 정렬 과정을 마친 뒤의 최종 위치가 된다. 즉 해당 위치를 결정하고, 그 왼쪽과 오른쪽 요소들에 대해 다시 Quicksort를 진행...을 반복하는 방식이다.
• in-place(제자리 정렬): merge sort와 비교되는 quick sort의 장점. 메모리를 덜 필요로 한다.
• 평균적으로 O(nlogn): pivot을 어떻게 설정하느냐에 따라 달라질 수 있다.
• unstable(불안정적): 멀리 떨어진 위치로 요소를 이동시키게 되므로 unstable하게 될 가능성이 존재한다.

다음으로는 Lomuto's Partition Scheme을 보자. partition하는 방식이 완전히 다르며, main 메소드에서 quickSort를 call할 때 마지막 매개변수에 차이가 있다.

	public class Main {
	public static void main(String[] args) {
	int[] intArray = { 49, 75, 10, 4, 56, -3 };
	quickSort(intArray, 0, intArray.length - 1);
	}
	/** Lomuto 's partition scheme **/
	public static int partition(int[] input, int start, int end) {
	int pivot = input[end]; // Pivot is the last element of the sub-array
	int i = start; // The last index of the left-side array
	for (int j = start; j < end; j++) {
	if (input[j] < pivot) {
	swap(input, i, j);
	i++;
	}
	}
	swap(input, i, end);
	return i;
	}
	public static void quickSort(int[] input, int start, int end) {
	// if (end - start < 2) return;
	if (start == end) return;
	if (end - start == 1) {
	if (input[start] > input[end])
	swap(input, start, end);
	}
	if (start < end) {
	int pivotIndex = partition(input, start, end);
	quickSort(input, start, pivotIndex - 1);
	quickSort(input, pivotIndex + 1, end);
	}
	}
	public static void swap(int[] input, int i, int j) {
	int temp = input[i];
	input[i] = input[j];
	input[j] = temp;
	}
	}

view raw QuickSort.java hosted with ❤ by GitHub