[Sorting] 퀵 정렬

저번 포스팅에서는 분할 정복 알고리즘을 사용한 Merge Sort에 대해 알아보았다. 최악과 최선 모두 O(nlogn)의 시간 복잡도를 가지고 있어 데이터의 양이 많아도 항상 일정한 속도를 유지할 수 있다. Quick Sort 역시 분할 정복 알고리즘을 활용한 정렬방법이다. 나누는 기준점에 따라 최악의 경우 O(n^2)이 걸리기도 하지만 보통 O(nlogn)의 시간이 걸린다. 그럼에도 불구하고 퀵 정렬은 높은 효율을 보인다. 더 깊이 알아보도록 하자.

---

Quick Sort

데이터 집합에서 하나의 Pivot(기준점 데이터)을 잡는다. 왼쪽에는 Pivot보다 작은 값을, 오른쪽에는 Pivot보다 큰 값들로 나누어 분리한다. 분리가 되었다면 Pivot의 데이터는 자신의 위치를 찾게 된다. 이후 다시 정렬이 안된 부분들의 Pivot을 설정하여 부분 집합들을 다시 정렬한다.

• In-place Sorting(제자리 정렬)
• Unstable Sorting(불안정 정렬)

위 그림에서는 기준점을 부분 집합의 가장 앞 데이터로 설정하였다. 가장 앞 데이터를 pivot으로 삼은 것이 큰 의미가 있는 것이 아니므로 참고하기 바란다.

 

Pivot의 기준?  

결정되는 Pivot에 따라 O(n^2)의 시간이 소요될 수도 있고(최악), O(nlogn)이 소요될 수도 있다(평균 or 최선). 그렇다면 언제 O(n^2)의 시간이 걸릴 수 있을까?  이미 데이터 집합이 정렬되어 있을 경우 위 그림처럼 가장 앞 데이터인 제일 작은 데이터를 pivot으로 지정해보자.

퀵 정렬의 정렬 속도가 빠르려면 분할 정복 알고리즘 특성 상 pivot을 기준으로 반으로 나눠지고, 부분 집합 내에서 다시 pivot을 설정해 빠르게 정렬해나가야 한다. 하지만 위의 경우처럼 이미 정렬되어 있으면 제기능을 발휘하지 못한다. 따라서 O(n^2)의 시간이 걸리는 것이다. 반면에 데이터 집합의 중간 값을 pivot으로 설정하면 어떨까? 중간 값이 pivot이 된다면 pivot을 기준으로 좌우의 부분 집합 데이터 크기는 비슷해지고, 동시에 부분 집합 데이터들이 정렬이 되어질 것이다.

 

 

정렬과정

1. 임의의 데이터를 pivot으로 설정한다.
2. pivot 다음을 가리키는 인덱스를 left, 배열의 마지막을 가리키는 인덱스 right로 설정
3. left는 오른쪽으로 이동하며 pivot 보다 작은 값을 찾는다. 찾으면 대기.
4. right는 왼쪽으로 이동하며 pivot 보다 큰 값을 찾는다. 찾으면 대기.
5. left가 가리키는 데이터와 right가 가리키는 데이터의 위치를 서로 교환한다.
6. left와 right가 서로 만나거나 넘어선 경우에는 right와 pivot의 위치를 교환한다.
7. pivot의 위치를 고정하고, pivot의 왼쪽 부분 집합 데이터와, 오른쪽 부분 집합 데이터를 다시 정렬한다.

위처럼 로직을 구현하여 퀵 정렬을 할 수도 있지만 이렇게 하면 코드 내부에 반복 코드들이 많이 작성될 것이다. left를 오른쪽으로 이동시키고, right를 왼쪽으로 이동 시켜야 하기 때문이다. left와 right를 같이 왼쪽에서 오른쪽으로 이동시키면서 정렬할 수도 있다.

 

다음과 같은 방법을 자바 코드로 나타내면

import java.util.Scanner;

/*input data:
8
51287346
*/
public class quick {

    static int N;                      // 입력할 데이터의 개수
    static int arr[];                  // 입력될 데이터 집합

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        arr = new int[N];

        for(int i = 0; i< N; i++)
            arr[i] = sc.nextInt();

        quickSort(0, N-1);   //데이터 집합의 처음 인덱스와 마지막 인덱스 정보 제공

        for(int i : arr)
            System.out.print(i + " ");

    }

    static void quickSort(int left, int right) {
        int pivotIdx;
        
        if(left < right)
        {
            pivotIdx = partition(left, right);
            quickSort(left, pivotIdx - 1);
            quickSort(pivotIdx + 1, right);
        }
    }

    static int partition(int left, int right){
        int pivot = arr[left];    //pivot으로 배열의 첫번째 원소로 설정한다.
        int j = left;             // swap할 때 기준으로 j는 pivot보다 큰 값을 가리킨다.
        for(int i = left + 1; i <= right; i++) {
            if(arr[i] < pivot)    // 데이터가 pivot 보다 작을 때 j의 인덱스와 i의 인덱스를 서로 교환한다.
            {
                j++;
                if(i != j)
                    swap(i, j);
            }
        }
        swap(left, j);       // 최종으로 pivot과 j의 데이터를 교환한다. 이때 j의 데이터는 위의 for 루프에서 swap된 다음의 데이터로 pivot 보다 작은 값을 가리킨다.
        return j;             // 최종 pivot의 위치를 넘겨준다. 
    }

    static void swap(int fIdx, int sIdx) {
        int temp = arr[fIdx];
        arr[fIdx] = arr[sIdx];
        arr[sIdx] = temp;
    }
}

 

Quick Sort의 장점

• O(nlogn)의 시간 복잡도를 가지는 다른 정렬 방법과는 다르게 pivot으로 설정된 값은 다음 정렬 단계에서 이미 정렬된 것으로 간주되어 포함되지 않는다. 따라서 가장 빠르다.

ex)
if(left < right){
    pivotIdx = partition(left, right);
    quickSort(left, pivotIdx - 1);
    quickSort(pivotIdx + 1, right);
}

• 추가적인 메모리 공간이 필요하지 않다.

결론

Quick Sort는 정렬 알고리즘 중에서 가장 빠른 편에 속한다. Pivot으로 설정된 값은 나중에 비교 연산에서 제외되므로 호출의 깊이가 깊어질수록 전체 데이터 개수에서 비교가 필요한 연산이 줄어든다.

Quick Sort가 매번 좋은 성능을 내려면 주어진 집합 내에서 중간 값을 pivot으로 설정해야 한다. 한가지 방법으로는 임의의 데이터들을 뽑아 중간값을 가져와 pivot으로 설정하는 것도 나쁘지 않다.

 

---

참고하면 좋은 사이트

알고리즘 - Quick(퀵) vs Merge(병합) 정렬(+TCO, 참조 지역성)

신입 개발자 기술면접 질문 정리 - 알고리즘