자바로 구현하는 퀵정렬 (Quick Sort) 알고리즘

 

퀵 정렬(QuickSort) 이란?

 

분할 작업을 순환적으로 반복하면서 피봇의 왼쪽 왼쪽 부분 집합과 오른쪽 부분집합을 정렬 하는 방법

1. 전체원소 가운데 하나의 원소를 중심(Pivot)으로 2개의 부분 집합으로 분할 한다.

2. 기준값(Pivot) 보다 작은 원소는 왼쪽 부분집합으로, 기준값(Pivot) 보다 큰 원소들은 오른쪽 부분 집합으로 정렬한다.

3. 분할된 부분집합의 크기가 0이나 1이 될 때 까지 순환 호출을 이용하여 다시 분할 한다.

 

위 과정을 반복하는 것이 퀵정렬 입니다.

출처 - http://ko.wikipedia.org/wiki/%ED%80%B5_%EC%A0%95%EB%A0%AC

 

 

 

C로 배우는 쉬운 자료구조 (한빛미디어) 서적의 수도코드 (pseudo code) 를 참고 하였으며,

서적의 수도코드를 기반으로 아래 자바 소스코드는 직접 제작하였음을 알려드립니다.

 

 

수도 코드

quickSort(a[], begin, end) 
	if (begin < end) then 
	  p ← partition(a, begin, end);
	  quickSort(a[], begin, p-1);
	  quickSort(a[], p+1, end);
	end if
end


partition(a[], begin, end)
	pivot ← (begin + end)/2;
	L ← begin;
	R ← end;
	while(L<R) do
		while(a[L] < a[pivot] and L<R) do L++;
		while(a[R] > a[pivot] and L<R) do R--;
		if (L<R) then
			temp ← a[L];
			a[L] ← a[R];
			a[R] ← temp;
		end if
	end while
end

 

퀵 정렬 알고리즘은 주어진 배열 a[]를 두개의 파티션으로 분할하는 연산이 필요합니다.

또한, 성능은 피봇에 의해 결정 됩니다.

 

피봇을 결정하는데에는 크게 두가지 방법이 있는데,

(1) 난수 분할(랜덤)

(2) 중위법 (좌측 끝, 중앙, 우측 끝)

난수 분할은 성능과 안정성이 떨어지기 때문에, 중위법 (중앙) 에서 분할 작업이 이루어 진다.

위 수도코드 역시 중앙에서 분할작업을 한다.

 

 

소스코드

 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

public static int partition(int arr[], int left, int right) { int pivot = arr[(left + right) / 2]; while (left < right) { while ((arr[left] < pivot) && (left < right)) left++; while ((arr[right] > pivot) && (left < right)) right--; if (left < right) { int temp = arr[left]; arr[left] = arr[right]; arr[right] = temp; } } return left; } public static void quickSort(int arr[], int left, int right) { if (left < right) { int pivotNewIndex = partition(arr, left, right); quickSort(arr, left, pivotNewIndex - 1); quickSort(arr, pivotNewIndex + 1, right); } }

 

 

이제 임의의 리스트 arrs 를 퀵정렬로 정렬 해보겠습니다.

 

1 2 3 4 5 6 7 8 9

public static void main(String[] args) { int[] arrs = { 69, 10, 30, 2, 16, 8, 31, 22 }; quickSort(arrs, 0, arrs.length - 1); System.out.println("결과"); for (int i : arrs) { System.out.print(i + " "); } }

 

실행 결과