[Algorithm] 퀵정렬 (Quick Sort)

퀵정렬이란?

하나의 리스트를 피벗(pivot)을 기준으로 두 개의 부분리스트로 나누어 하나는 피벗보다 작은 값들의 부분리스트, 다른 하나는 피벗보다 큰 값들의 부분리스트로 정렬한 다음, 각 부분리스트에 대해 다시 위 처럼 재귀적으로 수행하여 정렬하는 방법입니다.

 

구현 방법 3가지

 

중간 피봇(Median-of-three pivot):
장점: 배열의 처음, 중간, 끝 요소 중 중간값(median)을 피봇으로 선택하여 최악의 경우 시간복잡도를 줄일 수 있습니다.
단점: 추가적인 계산이 필요하고 구현이 다소 복잡할 수 있습니다.

왼쪽 피봇(Leftmost pivot):
장점: 구현이 간단하고 메모리 사용이 적습니다.
단점: 이미 정렬된 배열이나 역으로 정렬된 배열에서 최악의 성능을 보일 수 있습니다.

 

오른쪽 피봇(Rightmost pivot):
장점: 구현이 간단하고 왼쪽 피봇과 마찬가지로 메모리 사용이 적습니다.
단점: 이미 정렬된 배열이나 역으로 정렬된 배열에서 최악의 성능을 보일 수 있습니다.

 

 

왼쪽 피봇과 오른쪽 피봇은 이미 정렬된 배열에서 최악의 성능을 보일 수 있습니다!

그래서 중간 피봇 퀵정렬이 선호가 되긴 합니다.

 

 

 퀵 정렬은 기본적으로 '분할 정복' 알고리즘을 기반으로 정렬되는 방식입니다.

다만, 병합정렬(Merge Sort)과 다른 점은 병합정렬의 경우 하나의 리스트를 '절반'으로 나누어 분할 정복을 하고,

퀵 정렬(Quick Sort)의 경우 피벗(pivot)의 값에 따라 피벗보다 작은 값을 갖는 부분리스트와 피벗보다 큰 값을 갖는 부분리스트의 크기가 다를 수 있기 때문에 하나의 리스트에 대해 비균등하게 나뉜다는 점이 있습니다.

 

 

퀵소트는

• 비교 정렬
• 제자리 정렬
• 불안정 정렬

입니다.

 

 

중간 피봇을 가장 많이 사용하기 때문에 코드는 중간 피봇 선택 방식만 보도록 하겠습니다.

 

 

 

구현

public class QuickSort {
	
	public static void sort(int[] a) {
		m_pivot_sort(a, 0, a.length - 1);
	}
	
	/**
	 *  중간 피벗 선택 방식
	 * @param a		정렬할 배열
	 * @param lo	현재 부분배열의 왼쪽
	 * @param hi	현재 부분배열의 오른쪽
	 */
	private static void m_pivot_sort(int[] a, int lo, int hi) {
		
		/*
		 *  lo가 hi보다 크거나 같다면 정렬 할 원소가 
		 *  1개 이하이므로 정렬하지 않고 return한다.
		 */
		if(lo >= hi) {
			return;
		}
		
		/*
		 * 피벗을 기준으로 요소들이 왼쪽과 오른쪽으로 약하게 정렬 된 상태로
		 * 만들어 준 뒤, 최종적으로 pivot의 위치를 얻는다.
		 * 
		 * 그리고나서 해당 피벗을 기준으로 왼쪽 부분리스트와 오른쪽 부분리스트로 나누어
		 * 분할 정복을 해준다.
		 * 
		 * [과정]
		 * 
		 * Partitioning:
		 *
		 *      left part      a[(right + left)/2]      right part      
		 * +---------------------------------------------------------+
		 * |    element < pivot    |  pivot  |    element >= pivot   |
		 * +---------------------------------------------------------+
		 *    
		 *    
		 *  result After Partitioning:
		 *  
		 *         left part         a[hi]          right part
		 * +---------------------------------------------------------+
		 * |   element < pivot    |  pivot  |    element >= pivot    |
		 * +---------------------------------------------------------+
		 *       
		 *       
		 *  result : pivot = hi     
		 *       
		 *
		 *  Recursion:
		 *  
		 * m_pivot_sort(a, lo, pivot)         m_pivot_sort(a, pivot + 1, hi)
		 *  
		 *         left part                           right part
		 * +-----------------------+             +-----------------------+
		 * |   element <= pivot    |             |    element > pivot    |
		 * +-----------------------+             +-----------------------+
		 * lo                pivot          pivot + 1                   hi
		 * 
		 */
		int pivot = partition(a, lo, hi);	
		
		m_pivot_sort(a, lo, pivot);
		m_pivot_sort(a, pivot + 1, hi);
	}
	
	
	
	/**
	 * pivot을 기준으로 파티션을 나누기 위한 약한 정렬 메소드
	 * 
	 * @param a		정렬 할 배열 
	 * @param left	현재 배열의 가장 왼쪽 부분
	 * @param right	현재 배열의 가장 오른쪽 부분
	 * @return		최종적으로 위치한 피벗의 위치(hi)를 반환
	 */
	private static int partition(int[] a, int left, int right) {
		
		// lo와 hi는 각각 배열의 끝에서 1 벗어난 위치부터 시작한다.
		int lo = left - 1;
		int hi = right + 1;
		int pivot = a[(left + right) / 2];		// 부분리스트의 중간 요소를 피벗으로 설정
		
 
		while(true) {
			
			/*
			 * 1 증가시키고 난 뒤의 lo 위치의 요소가 pivot보다 큰 요소를
			 * 찾을 떄 까지 반복한다.
			 */
			do { 
				lo++; 
			} while(a[lo] < pivot);
 
			
			/*
			 * 1 감소시키고 난 뒤의 hi 위치가 lo보다 크거나 같은 위치이면서
			 * hi위치의 요소가 pivot보다 작은 요소를 찾을 떄 까지 반복한다.
			 */
			do {
				hi--;
			} while(a[hi] > pivot && lo <= hi);
			
			
			/*
			 * 만약 hi가 lo보다 크지 않다면(엇갈린다면) swap하지 않고 hi를 리턴한다.
			 */
			if(lo >= hi) {
				return hi;
			}
			
			
			// 교환 될 두 요소를 찾았으면 두 요소를 바꾼다.
			swap(a, lo, hi);
		}
		
	}
	
	
	
	private static void swap(int[] a, int i, int j) {
		int temp = a[i];
		a[i] = a[j];
		a[j] = temp;
	}
	
}

 

 

장점

1.

특정 상태가 아닌 이상 평균 시간 복잡도는 NlogN이며,

다른 NlogN 알고리즘에 비해 대체적으로 속도가 매우 빠릅니다.

유사하게 NlogN 정렬 알고리즘 중 분할정복 방식인 merge sort에 비해 2~3배정도 빠릅니다.

2.

추가적인 별도의 메모리를 필요로하지 않으며 재귀 호출 스택프레임에 의한 공간복잡도는 logN으로 메모리를 적게 소비합니다.

 

단점

 

1. 특정 조건하에 성능이 급격하게 떨어집니다.(이미 정렬이 되어있을 경우 등)

 

2. 재귀를 사용하기 떄문에 재귀를 사용하지 못하는 환경일 경우 그 구현이 매우 복잡해집니다.

 

 

 

출처:https://st-lab.tistory.com/250

자바 [JAVA] - 퀵 정렬 (Quick Sort)