퀵 정렬(Quick Sort)

퀵 정렬(Quick Sort)

정말 간략하게 핵심만 설명하겠습니다... ㅎㅎ

퀵 정렬은 기본적으로 분할정복입니다. 분할정복이기 때문에, 재귀적인 호출을 사용합니다.

우선 Pivot 즉 비교기준이 되는 값을 정하고, Left와 Right 각 2개의 비교대상을 정해서 비교하게 됩니다.

Left는 Pivot 보다 작은 경우 더 이상 index가 증가하지 않고 진행을 멈춥니다. 만약 크다면, 계속 index를 증가시키면서 Pivot과 비교해나갑니다.

Right는 Pivot보다 큰 경우 더이상 index가 감소하지 않고 진행을 멈춥니다. 만약 작다면, 계속 index를 감소시키면서 Pivot과 비교해나갑니다.

이 2case에 비교가 끝나고, 만약 Left의 index와 Right의 index가 교차하지 않고 Left <= Right 조건을 만족하면 각 index가 가리키고 있는 값들을 스위치 합니다. 

이런 프로세스는 각각의 index 가 서로 교차되지 않는 순간까지 반복합니다.

만약 교차가 되는 경우 재귀호출을 통해 Pivot의 값을 갖는 index를 기준으로 왼쪽/오른쪽을 나누고 왼쪽 분할정복이 가능한 경우를 체크하며, 분할정복이 가능한 때 분할정복을 진행합니다. 오른쪽도 마찬가지입니다.

Pivot를 정하는 기준은 보통 정렬할 대상이 되는 data 크기의 절반으로 중간 index를 설정합니다. 그 이유는 효과적으로 비교할 수 없는(?) 값이 Pivot으로 설정됬을 때 ,최악으로 정렬하는 경우를 방지하기 위해서 입니다.

저는 주 언어가 JAVA라서 JAVA로 구현해봤습니다. 

package EscapeStudy.sort;

import java.util.Arrays;

public class QuickSort {

	public static void main(String[] args) {
		int data[] = { 66, 10, 1, 34, 5, -10 };

		QuickSort quick = new QuickSort();
		quick.sort(data, 0, data.length - 1);

		System.out.println(Arrays.toString(data));

	}

	public void sort(int[] data, int l, int r) {
		int left = l;
		int right = r;
		int pivot = data[(l + r) / 2]; // pivot 가운데 설정 (최악의 경우 방지)

		do {
			while (data[left] < pivot)
				left++;
			while (data[right] > pivot)
				right--;

			if (left <= right) {
				System.out.println("change");
				int temp = data[left];
				data[left] = data[right];
				data[right] = temp;
				left++;
				right--;
			}
			System.out.println(Arrays.toString(data)+"	"+pivot);
			System.out.println("left : " + left + " right : " + right);
		} while (left <= right);

		if (l < right) {//분할정복시 더 이상 분할 것이 없는 경우 체크 (왼쪽 분할할 수 있는지 체크)
			System.out.println("l : " + l + " end: " + right);
			sort(data, l, right);
		}
		if (r > left) {//분할정복시 더 이상 분할 것이 없는 경우 체크 (오른쪽 분할할 수 있는지 체크)
			System.out.println("l : " + left + " end: " + r);
			sort(data, left, r);

		}
	}

}