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

정렬 알고리즘
1. Bubble Sort(거품 정렬)
2. Selection Sort(선택 정렬)
3. Insertion Sort(삽입 정렬)
4. Quick Sort(퀵 정렬) ⇠
5. Merge Sort(병합 정렬)
6. Heap Sort(힙 정렬)
7. Radix Sort(기수 정렬)
8. Counting Sort(계수 정렬)

기본 개념

• 병합 정렬과 마찬가지로 분할 정복(Divide and Conquer) 기법과 재귀 알고리즘을 이용한 정렬 알고리즘이다.
• 불안정 정렬에 속하며, 다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬에 속한다.
• 병합 정렬과 달리 배열을 비균등하게 분할한다.
• n개의 데이터를 정렬할 때 최악의 경우에는 O(N^2)번의 비교를 수행하고, 평균적으로 O(NlogN)번의 비교를 수행한다.
• 퀵 정렬의 내부 루프는 대부분의 컴퓨터 아키텍처에서 효율적으로 작동하도록 설계되어 있다.
  (∵ 메모리 참조가 지역화되어 있기 때문에 CPU 캐시의 히트율(캐시 적중률)이 높아지기 때문이다.)
  대부분의 실질적인 데이터를 정렬할 때 제곱 시간이 걸릴 확률이 거의 없도록 알고리즘을 설계하는 것이 가능하다. 또한 매 단계에서 적어도 1개의 원소가 자기 자리를 찾게 되므로 이후 정렬할 개수가 줄어든다. 그렇기에 일반적인 경우 퀵 정렬은 다른 O(NlogN) 알고리즘에 비해 훨씬 빠르게 동작한다.

특징

• 자바의 Arrays.sort() 처럼 프로그래밍 언어 차원에서 기본적으로 지원되는 내장 정렬 함수는 대부분은 퀵 정렬을 기본으로 한다.
• 일반적으로 원소의 개수가 적어질수록 나쁜 중간값이 선택될 확률이 높아지기 때문에, 원소의 개수에 따라 퀵 정렬에 다른 정렬을 혼합해서 쓰는 경우가 많다.
• 병합 정렬과 퀵 정렬은 분할 정복과 재귀 알고리즘을 사용한다는 측면에서 유사해보이지만, 내부적으로는 정렬을 하는 방식에는 큰 차이가 있다.
• 병합 정렬은 항상 정중앙을 기준으로 단순 분할 후 병합 시점에서 값의 비교 연산이 발생하는 반면,
  퀵 정렬은 분할 시점부터 비교 연산이 일어나기 때문에 그 이후 병합에 들어가는 비용이 매우 적거나 구현 방법에 따라서 아예 병합을 하지 않을 수도 있다.

구현(Java)

• 하나의 리스트를 pivot을 기준으로 두 개의 비균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두 개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트가 되게 하는 방법이다.
• 과정
  Step1. 분할(Divide) : 입력 배열을 pivot을 기준으로 비균등하게 2개의 부분 배열(pivot을 중심으로 왼쪽 = pivot보다 작은 요소들, 오른쪽 = pivot 보다 큰 요소들)로 분할한다.
  Step2. 정복(Conquer) : 부분 배열을 정한다. 부분 배열의 크기가 충분히 작지 않으면 순환 호출을 이용하여 다시 분할 정복 방법을 적용한다.
  Step3. 결합(Combine) : 정렬된 부분 배열들을 하나의 배열에 합병한다.
• 순환 호출이 한번 진행될 때마다 최소한 하나의 원소(pivot)은 최종적으로 위치가 정해지므로, 이 알고리즘은 반드시 끝난다는 것을 보장할 수 있다.

public class Quick {
	public static void quickSort(int[] arr) {
    	sort(arr, 0, arr.length - 1);
    }
    
	public static void sort(int[] arr, int low, int high) {
    	if (low >= high) return;
        
        int mid = partition(arr, low, high);
        sort(arr, low, mid - 1);
        sort(arr, mid, high);
	}
    
    // 1. 정렬 범위를 인자로 받는다.
    // 2. 좌우측의 값들을 정렬하고 분할 기준점의 인덱스를 리턴한다.
    private static int partition(int[] arr, int low, int high) {
    	// 리스트의 정 가운데 값을 pivot으로 지정
    	int pivot = arr[(low+high)/2];
        while (low <= high) {
        	while (arr[low] < pivot) low++;		//pivot값 보다 크지만 좌측에 있는 값을 찾기 위해
            while (arr[high] > pivot) high--;   //pivot값 보다 작지만 우측에 있는 값을 찾기 위해
            // 두 인덱스가 아직 서로 교차해서 지나치지 않았다면
            // 시작 인덱스(low)가 가리키는 값과 끝 인덱스(high)가 가리키는 값을 교대(swap) 시킨다.
            // (∵ 잘못된 위치에 있는 두 값의 위치를 바꾸기 위해서)
            if (low <= high) {
            	swap(arr, low, high);
                low++;
                high--;
            }
        }
        return low;
    }
    
    private static void swap(int[] arr, int i, int j) {
    	int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
}

복잡도

• 공간복잡도 : 구현 방법에 따라 달라진다. 주어진 배열 안에서 swap을 진행하면 O(N)이다. 입력 배열이 차지하는 메모리만을 사용하는 in-place sorting 방식으로 구현을 사용할 경우, O(logN)의 공간 복잡도를 가진 코드의 구현이 가능하다.
• 시간복잡도 : 퀵 정렬의 성능은 pivot 값을 어떻게 선택하느냐에 따라 크게 달라질 수 있다. 이상적인 경우에는 pivot 값을 기준으로 동일한 개수의 작은 값들과 큰 값들이 분할되어 병합 정렬과 마찬가지로 O(NlogN) 의 시간복잡도를 가진다.
  pivot을 기준으로 partitioning을 진행하면 최대 n-1번까지 비교해야하므로 O(N) 의 시간이 걸리게 된다. 또 계속해서 pivot을 중위값으로 고르게 되면 데이터는 절반으로 쪼개지며 배열의 길이가 1이 될 때까지 logN번 분할을 하게 된다. 그래서 총 O(NlogN) 의 시간복잡도를 가지게 된다.
• 하지만 pivot 값을 기준으로 분할했을 때 값들이 한 편으로 크게 치우치게 되면, 퀵 정렬은 성능이 저하되게 되며, 최악의 경우 한 편으로만 모든 값이 몰리게 되어 분할을 할 때 N-1번을 쪼개야하면서 O(N^2) 의 시간 복잡도를 보이게 된다.
• 따라서 상용 코드에서는 중앙값(median)에 가까운 pivot 값을 선택할 수 있는 전략이 요구되며, 배열의 첫값과 중앙값 그리고 마지막값 중에 크기가 중간인 값을 사용하는 방법이 많이 사용된다.