[Algorithm] 정렬 - Quick Sort (퀵 정렬)

Quick Sort

• 특정 원소(pivot)를 기준으로 왼쪽은 lower, 오른쪽은 upper 원소들을 두는 방식
• Merge Sort와 마찬가지로 Divide and Conquer 알고리즘
• 불안정 정렬(unstable sort)
  • 안정 정렬(stable sort): 비교하는 원소의 값이 같을 때 input 순서대로 정렬
• 평균적으로 \(O(nlogn)\)의 시간복잡도를 가지며, 매 Step마다 적어도 한 개의 원소는 반드시 자기 자리를 찾아가므로 매우 빠름
  • 하지만 최악의 경우에 \(O(n^2)\)의 시간복잡도를 가짐

  • 

 

동작

Step 1

 

Step 2

 

Step 3

 

Step 4

 

코드

public class Sort {
	
    public void quickSort(int[] arr, int first, int last) {
        if(first < last) {
            int pivot = partition(arr, first, last);
            quickSort(arr, first, pivot - 1);
            quickSort(arr, pivot + 1, last);
        }
    }
    
    public int partition(int[] arr, int first, int last) {
    	int pivot = arr[last];
        int i = first - 1;
        
        for(int j = first; j < last; j++) {
            if(arr[j] < pivot) {
            	swap(arr, ++i, j);
            }
        }
        swap(arr, i + 1, pivot);
        
        return i + 1;
    }
    
    public void swap(int[] arr, int index1, int index2) {
    	int temp = arr[index1];
        arr[index1] = arr[index2];
        arr[index2] = temp;
    }
}

 

왜 최악의 경우에는 \(O(n^2\)일까?

 

• 최선의 경우: 매 Step마다 원소가 중앙에 위치되어서 반으로 나누어지는 경우

 

• 최악의 경우: 매 Step마다 원소가 끝에 위치되어서 1 : 9 로 나누어지는 경우 (이미 정렬된 배열)

그래서 pivot을 선택하는 여러 variation 기법이 존재한다. (Randomized Quick Sort 등..)