정렬 알고리즘 - 퀵 정렬

퀵 정렬 (Quick Sort)

분할 정복법

- 분할 : 배열을 아래의 조건이 되도록 두 부분으로 나눈다. (Pivot을 이용한다.)

lower part elements ≤ upper part elements

- 정복 : 각 부분을 순환적으로 정렬한다.

- 합병 : 수행하지 않는다.

퀵 정렬 수행 과정

- 정렬할 배열이 주어진다. 이 때 마지막 수를 기준 (pivot)으로 삼아둔다.

31 8 48 73 11 3 20 29 65 15(pivot)

- 기준보다 작은 수는 기준의 왼쪽에, 나머지는 기준의 오른쪽에 오도록 재배치 (분할)한다.

8 11 3 15 31 48 20 29 65 73

- 기준의 왼쪽과 오른쪽을 각각 순환적으로 정렬한다.

퀵 정렬 슈도 코드

quickSort (A[], p, r) {

if (p < r) {

q = partition (A, p, r); // 분할

quickSort (A, p, q - 1); // 피벗 기준 왼쪽 정렬

quickSort (A, q, r); // 피벗 기준 오른쪽 정렬

} // 만일 p가 r보다 크거나 같다면 정렬할 원소가 0이거나 1이라는 뜻이다.

}

partition (A[], p, r) {

배열 A의 원소들을 A[r]기준으로 양쪽으로 재배치한 후 A[r]이 자리한 인덱스를 반환해준다.

}

- 파티션의 슈도 코드

대략적인 과정으로는 피벗을 맨 뒤에 가만히 둔채로 작은 값과 큰 값을 정렬한 후 큰 값중 첫번째 인덱스와 피벗의 위치를 바꾸어주는 것이다.

i는 기준보다 작은 값들 중 마지막 값이며, j는 피벗과 비교하려는 값을 의미한다.

partition {

if A[j] >= x

j <- j + 1;

else

j <- i + 1;

exchange A[i] and A[j];

j <- j + 1;

}

- 피벗을 이용한 파티션 과정

Partition (A, p, r) {

x <- A[r];

// 초기에는 피벗보다 작은 값이 있는지 모르기 때문에 p의 최소값보다 1 더 적게 하여 아예 밖을 가리키게 한다.

i <- p - 1; 

for j <- p to r -1

if A[j] ≤ x

i <- i + 1;

exchange A[i] and A[j];

exchange A[i + 1] and A[r];

return i + 1;

}

-> 파티션 함수가 동작하는 시간은 데이터를 n개라 하였을 때 모든 데이터를 한 번씩 비교해야 하기 때문에 n - 1의 시간이 걸리게 되고, 최종적으로는 O(n)의 시간이 걸린다고 할 수 있다.

퀵 정렬이 최악의 경우가 나올 때

- 항상 한 쪽은 0개, 다른 쪽은 n - 1개로 분할되는 경우

T(n) = T(0) + T(n - 1) + Θ(n)

= T(n - 1) + Θ(n)

= T(n - 2) + T(0) + Θ(n - 1) + Θ(n)

...

= Θ(1) + Θ(2) + ... + Θ(n - 1) + Θ(n)

= Θ($n^2$)

- 이미 정렬된 입력 데이터 (만일 마지막 원소를 피벗으로 설정하였을 때)

- 최악의 경우 합병 정렬의 시간복잡도인 O(n logn)과 비교했을 때 더 효율이 떨어지는 결과라고 할 수 있다.

퀵 정렬이 최선의 경우가 나올 때

- 항상 정확하게 절반으로 분할되는 경우

T(n) = 2T(n / 2) + Θ(n)

= Θ(n logn)

- 합병 정렬과 같은 루틴을 보이게 된다.

- 퀵 정렬이 많이 쓰이는 이유는 최악의 경우에는 시간복잡도가 $n^2$임에도 실제로는 그런 상황이 거의 발생하지 않기 때문에 

평균적인 시간 복잡도

- 일반적인 다른 정렬들에 경우에는 평균 시간 복잡도를 구하기 어렵다는 이유로 잘 계산하지 않는다. 하지만 퀵 정렬에 경우에는 알고리즘이 비교적 단순하기 때문에 평균 시간 복잡도를 구하기에 어려움이 적다.

- A(n) = $\sum _{ \forall InputInstanceIOfSizeN }^{  }{ p(I)T(I) } $

(p(I) : I가 입력으로 들어올 확률 / T(I) : I를 정렬하는 데 걸리는 시간)

데이터가 n개라고 할 때 가능한 모든 입력 I에 대해 p(I)와 T(I)의 곱의 합들이다.

- 위의 식에서 정확한 p(I)값을 모른다는 문제점이 있다.

- 문제점을 해결하기 위해 p(I)에 대한 가정을 한 후 분석을 수행하게 된다.

- Ex) 모든 입력 인스턴스가 동일한 확률을 가진다고 할 때 $p(I) = \frac { 1 }{ n! }$

Pivot을 선택하는 방법들

- 첫번째 값이나 마지막 값을 피벗으로 선택

1) 이미 정렬된 데이터나 거꾸로 정렬된 데이터가 최악의 경우

2) 현실의 데이터는 무작위가 아니기 때문에 (거꾸로)정렬된 데이터가 입력으로 들어올 가능성은 매우 높다.

3) 이 방식은 좋은 방식이라고 할 수 없음

- "Median of Three"

1) 첫번째 값과 마지막 값, 그리고 가운데 값 중에 중간값(median)을 피벗으로 삼는다.

2) 최악의 경우가 발생했을 때의 시간복잡도는 위의 방식과 차이가 없다.

- Randomized Quicksort

1) 피벗을 무작위 위치에서 선택한다.

2) no worst case instance, but worst case execution

3) 평균 시간복잡도는 O(n logn)이 된다.

코드 구현

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.StringTokenizer;
 
//2019-05-27
//퀵 정렬을 구현한 프로그램이다.
//합병정렬과 마찬가지로 ArrayOutOfBoundException으로 인해
//배열의 처음과 끝 인덱스를 계산하는데 시간을 많이 소요하였다.
public class QuickSort {
    static BufferedWriter bw;
    static int[] inputArray;
    
    public static void main(String[] args) throws Exception {
        init();
        sorting(inputArray, 1, inputArray.length);
        printArray(inputArray);
    }
    
    static void init() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        bw.write("정렬하고자 하는 수를 입력해주세요 : ");
        bw.flush();
        
        int index = 0;
        String input = br.readLine();
        StringTokenizer st = new StringTokenizer(input);
        inputArray = new int[st.countTokens()];
        
        while (st.hasMoreTokens())
            inputArray[index++] = Integer.parseInt(st.nextToken());
    }
    
    static void printArray(int[] array) throws Exception {
        bw.write("정렬된 결과 배열은 " + Arrays.toString(array) + "입니다.");
        bw.close();
    }
    
    static void sorting(int[] inputArray, int start, int end) {
        int middle;
        
        if (start < end) {
            middle = partition(inputArray, start, end);
            sorting(inputArray, start, middle - 1);
            sorting(inputArray, middle, end);
        }
    }
    
    static int partition(int[] array, int start, int end) {
        int comp = array[end - 1];
        int i = start - 1;
        
        for (int j = start - 1; j < end; j++) {
            if (array[j] < comp) {
                change(array, i, j);
                i++;
            }
        }
        
        change(array, i, end - 1);
        
        return i + 1; //피벗의 위치는 i + 1번째에 위치
    }
    
    static void change(int[] array, int a, int b) {
        int tmp = array[a];
        array[a] = array[b];
        array[b] = tmp;
    }
}