Quicksort from CTCI

코딩 인터뷰 완전 분석(원제: Cracking the Coding Interview)에 소개된 Quicksort를 다시 한 번 정리 해보려고 한다.

기본적으로 퀵정렬은, 무작위로 한 원소를 정하고(이를 pivot이라 부른다), pivot보다 작은 원소들은 앞쪽에, 큰 원소들은 뒷쪽에 위치시킨다. 

• 실행시간: 평균 O(n logn), 최악 O(n^2).
• 메모리: O(logn)

배열 분할(partition)에 사용되는 원소(pivot)가 배열의 중간값(median) 혹은 중간값에 가까운 값이라면 좋은 성능이 나오겠지만, 반드시 그러리라는 보장은 할 수 없다. 즉 퀵정렬은 pivot을 어떻게 정하느냐에 따라 느리게 동작할 수도 있으며, 최악의 경우 수행시간이 O(n^2)이 될 수 있다.

이전에 작성했던 퀵정렬(Hoare's Scheme)과 다른 점은, pivot을 배열의 첫번째 원소가 아니라 중간에 위치한 원소로 정한다는 것이다. 왼쪽에서는 pivot보다 큰 원소, 즉 왼쪽에서 오른쪽으로 옮겨줘야 하는 원소를 찾고, 오른쪽에서는 pivot보다 작은 원소, 즉 오른쪽에서 왼쪽으로 옮겨줘야 하는 원소를 찾은 뒤 swap하는 방식이다.

	public class QuickSortCtci {
	private static void quickSort(int[] arr, int left, int right) {
	int index = partition(arr, left, right);
	if (left < index - 1) quickSort(arr, left, index-1);
	if (index < right) quickSort(arr, index, right);
	}
	private static int partition(int[] arr, int left, int right) {
	int pivot = arr[(left+right)/2];
	while (left <= right) {
	while (arr[left] < pivot) left++;
	while (arr[right] > pivot) right--;
	if (left <= right) {
	swap(arr, left, right);
	left++;
	right--;
	}
	}
	return left;
	}
	private static void swap(int[] arr, int index1, int index2) {
	int tmp = arr[index1];
	arr[index1] = arr[index2];
	arr[index2] = tmp;
	}
	public static void main(String[] args) {
	int[] intArray = {20, 35, -15, 7, 55, 1, -22};
	quickSort(intArray, 0, intArray.length-1);
	for (int num : intArray) {
	System.out.print(num + " ");
	}
	}
	}

view raw QuickSortCtci.java hosted with ❤ by GitHub