[알고리즘] 퀵 정렬(Quick Sort)

퀵 정렬(Quick Sort)

• Divide and Conquer 알고리즘
• 하나의 문제를 작은 문제로 분할하여 해결해나가는 패러다임
• 재귀 알고리즘을 사용
• 안정적인 알고리즘은 아님

코드 설계

• Pivot이라는 값을 기준으로 파티셔닝(피벗을 선택하고 재정렬하는 프로세스)작업을 한다.

• Pivot을 기준으로 좌측에는 pivot보다 작은 값, 우측에는 보다 큰 값을 놓는다.

• Pivot을 기준으로 양쪽의 두 배열(세그먼트)들은 하위 문제로 놓고 재귀를 통해 다시 pivot 작업을 수행

• peudo-code

QuickSort(A, start, end) {
    if(start < end) {
        pIndex <- partition(A, start, end) // 파티션 작업 & pivot index 설정
        QuickSort(A, start, pIndex - 1) // 분할 작업
        QuickSort(A, pIndex + 1, end)
    }
}
partition(A, start, end) {
    pivot <- A[end]
    pIndex <- start
    for i <- start to end -1 {
        if (A[i] <= pivot) {
            swap(A[i], A[pIndex])
            pIndex <- pIndex + 1
        }
    }
    swap(A[pIndex], A[end])
    return pIndex
}

코드 구현

    /**
     * 1. pivot 설정
     * 2. partition 작업
     * 3. 분할 정복
     * @param A
     * @param start
     * @param end
     */
    private void quickSort(int[] A, int start, int end) {
        if (start < end) {
            int pIndex = partition(A, start, end);
            quickSort(A, start, pIndex - 1);
            quickSort(A, pIndex + 1, end);
        }
    }
    /**
     * 파티션 나누기
     * @param A
     * @param start
     * @param end
     * @return
     */
    private int partition(int[] A, int start, int end) {
        int pivot = A[end];
        int pIndex = start;

        for (int i = start; i < end; i++) {
            if (A[i] <= pivot) {
                // pivot 값보다 작거나 같은 경우 swap
                int tmp = A[i];
                A[i] = A[pIndex];
                A[pIndex] = tmp;

                pIndex++;
            }
        }
        // pivot 값을 센터로 이동
        int tmp = A[pIndex];
        A[pIndex] = A[end];
        A[end] = tmp;

        return pIndex;
    }

• 과정 출력

Pivot( 4 ) 값 설정 후 파티션 나누기: 
7    2    1    6    8    5    3    4    
2    7    1    6    8    5    3    4    
2    1    7    6    8    5    3    4    
2    1    3    6    8    5    7    4    
파티션 과정 완료 후 Pivot(4) 이동
2    1    3    4    8    5    7    6    

Pivot( 3 ) 값 설정 후 파티션 나누기: 
2    1    3    4    8    5    7    6    
2    1    3    4    8    5    7    6    
2    1    3    4    8    5    7    6    
파티션 과정 완료 후 Pivot(3) 이동
2    1    3    4    8    5    7    6    

Pivot( 1 ) 값 설정 후 파티션 나누기: 
2    1    3    4    8    5    7    6    
파티션 과정 완료 후 Pivot(1) 이동
1    2    3    4    8    5    7    6    

Pivot( 6 ) 값 설정 후 파티션 나누기: 
1    2    3    4    8    5    7    6    
1    2    3    4    5    8    7    6    
파티션 과정 완료 후 Pivot(6) 이동
1    2    3    4    5    6    7    8    

Pivot( 8 ) 값 설정 후 파티션 나누기: 
1    2    3    4    5    6    7    8    
1    2    3    4    5    6    7    8    
파티션 과정 완료 후 Pivot(8) 이동
1    2    3    4    5    6    7    8    

분석

• 복잡도 분석
  • Best & Average case O(nlogn)
  • Worst case O(n^2)
• O(n^2) 임에도 적절하게 빠른 정렬