퀵(Quick)정렬에 대해 알아봅시다

이번 포스팅에서는 퀵정렬의 개념과 방식에 대해 알아보고 자바로 구현해보겠습니다.

 

 

퀵정렬이란 ?

퀵정렬은 Divide and Conquer(분할정복) 알고리즘 중 하나입니다. 즉 문제를  작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아 원래의 문제를 해결하는 전략이죠. 분할정복 방식은 보통 순환 호출을 이용해 구현합니다. 이러한 분할정복 알고리즘의 특징은 평균적으로 매우 빠른 수행속도를 자랑한다는 것입니다.

    - Divide : 동일한 문제에 대해서 더 작은 부분으로 나누는 것

    - Conquer : 작은 부분들을 재귀적으로 해결하는 것

 

 

퀵정렬의 과정

그렇다면 퀵정렬은 어떻게 수행되는 걸까요? 무엇을 기준으로 Divide 해서 문제를 해결하는 걸까요?

여기에서 말하는 '기준'을 pivot(피봇)이라고 하고, 설명하겠습니다.

 

• 가장 먼저 정렬할 배열을 나눠줄 pivot을 선정해야 합니다. pivot을 선정하는 방법은 여러가지가 있지만, 배열 중 가장 가운데에 있는 값으로 설정하겠습니다. 그리고 퀵정렬이 수행되는 배열의 맨 왼쪽과 맨 오른쪽부터 각각 값을 탐색하기 시작합니다.
• 퀵정렬에서는 pivot보다 작은 값은 pivot의 왼쪽으로 / pivot보다 큰 값은 오른쪽으로 보내게 됩니다. 이러한 형태를 만들기 위해 pivot의 왼쪽에 있는 pivot보다 큰 값과 pivot의 오른쪽에 있는 pivot보다 작은 값을 서로 swap 해줍니다. 그리고 pivot을 기준으로 나누어진 값들 끼리 다시 순환 호출을 이용해 퀵정렬을 수행합니다.
• 더이상 분할이 불가능할 때까지 위 과정을 반복합니다.

 

그림으로 설명하자면 다음과 같습니다.

1. 배열의 가장 처음과 끝에서 각각 Left와 Right가 시작합니다. 피봇은 배열의 중앙(index 4)에 있는 값인 3으로 정해집니다.
2. L은 피봇인 3보다 값이 큰 수를 찾을 때까지, R은 3보다 작은 수를 찾을 때까지 이동합니다.
3. 해당 값을 각각 찾은 뒤 L과 R의 위치가 엮이지 않았다면 각 값들을 swap합니다.(5와 1)
4. 다음 swap할 값을 찾기 위해 L과 R은 다시 이동하다가 L은 6을 만나고 R은 피봇인 3을 만나(* 피봇도 포함합니다!) swap 해줍니다.
5. 다시 이동해 L은 10을 만나 멈추게 되고 R은 3에서 멈춰있어 R과 L의 위치가 바뀌게 되면 피봇인 3을 기준으로 3의 왼쪽에는 3보다 작은 수들만, 오른쪽에는 3보다 큰 수들만 존재함을 알 수 있습니다.
6. 이 때 Left(나누어진 오른쪽 배열 중 가장 첫번째)를 리턴해주고 이를 기반으로 Quick 정렬을 다시 수행합니다. 

 

퀵정렬의 시간복잡도

 

퀵 정렬 알고리즘에서 실행 성능은 Pivot에 의해 결정됩니다. 성능이 가장 좋은 경우는 정확히 n/2로 나뉘었을 때 입니다. 이 때, 최소이기 때문입니다. 반대로 n, n-1개로 나뉠 경우 한 쪽으로 치우쳐 수행 단계가 최대로 올라갈 경우 실행 성능이 최저로 떨어집니다. 평균 시간 복잡도는 아래와 같습니다.

 

 

 

퀵정렬 구현 (Java)

public class QuickSort {
	
	public static int partition(int[] arr, int left, int right) {
		
		int mid = arr[(left + right) / 2];
		int temp;
		
		while(left <= right){
			
			while(arr[left] < mid) {
				left++;
			}
			while(arr[right] > mid) {
				right--;
			}
			if(left <= right ) {
				temp = arr[right];
				arr[right] = arr[left];
				arr[left] = temp;
				
				left++;
				right--;
			}
			
		}
		
		return left;
	}
	
	public static void Quick(int[] arr, int left, int right) {
		
		int pivot = partition(arr, left, right);
	
		if(left < pivot - 1) {
			Quick(arr, left, pivot - 1);
		}
		if(pivot < right) {
			Quick(arr, pivot, right);	
		}
	}
	
	public static void main(String[] args) {
		
		int[] arr = { 2, 5, 6, 10, 3, 1, 4, 7, 9, 8};
		
		Quick(arr, 0, arr.length - 1);
		for(int i : arr) {
			System.out.println(i);
		}
	
	}
}