Quick Sort (partition exchange sort)

1. Problem

- n개의 key를 오름차순으로 정렬해보자

- 퀵 정렬은 특정 값(pivot)을 기준으로 그 값보다 작은 것과 큰 것으로 나눠서 정렬한다.

 

2. Input

1) 양수 n

2) 배열 S 1-indexed

 

3. Output

1) 오름차순으로 정렬된 S

 

4. PseudoCode

void quicksort(index low, index high){
    index pivotpoint;
    if(low<high){
        partition(low, high, pivotpoint); // pivot을 기준으로 작은 값과 큰 값으로 나눈다.
        quicksort(low, pivotpoint-1);     // 작은 값들에 대해 퀵 정렬을 한다.
        quicksort(pivotpoint+1, high);    // 큰 값들에 대해 퀵 정렬을 한다.
    }
}
 
void partition(index low, index high, index& pivotpoint){
    index i, j;
    keytype pivotitem = S[low]; // 맨 앞에 위치한 값을 pivot으로 정한다.
    j = low;                    // pivot보다 작은 값이 위치할 인덱스이다.
    for(i=low+1 ; i<=high ; i++) // pivot보다 뒤에 있는 값들에 대하여
        if(S[i]<pivotitem){      // i번째 값이 pivoit보다 작다면
            j++;                 // pivot 뒤쪽에 있는 값과
            exchange S[i] and S[j]; // i번째에 있는 값의 자리를 바꾼다.
        }
    pivotpoint = j; // 최종적으로 pivot값이 위치할 인덱스이다.
    exchange S[low] ans S[pivotpoint];
}

 

5. Example

class AlgoTest {
    public static void main(String[] args){
        int[] arr = {15,22,13,27,12,10,20,25};
        quicksort(0, arr.length-1, arr);
        for(int i : arr)
            System.out.print(i + " "); // 10 12 13 15 20 22 25 27 
    }

    static void quicksort(int low, int high, int[] S) {
        int pivotpoint = low; // pivotpoint를 기준으로 파티션
        for(int i=low; i<=high ; i++)
            if(S[low]>S[i])
                pivotpoint++;
        // 오름차순으로 정렬했을 때 S[low]가 위치할 곳 = pivotpoint
        if(low<high) {
            partition(low, high, pivotpoint, S);
            quicksort(low, pivotpoint-1, S);
            quicksort(pivotpoint+1, high, S);
        }
    }

    static void partition(int low, int high, int pivotpoint, int[] S) {
        int pivotitem = S[low], j = low;
        // pivotitem보다 작은 친구들을 앞으로 이동시키는 작업
        for(int i=low+1 ; i<=high ; i++)
            if(S[i]<pivotitem) {
                int tmp = S[i];
                S[i] = S[++j];
                S[j] = tmp;
            }
        pivotpoint = j;
        int tmp = S[low];
        S[low] = S[pivotpoint];
        S[pivotpoint] = tmp;
    }
}

- worst T(n) = O(n^2)

- average T(n) = O(n lg n)

 

6. 추가 내용

1) 퀵 정렬이 진행되는 예시

// 처음 배열: 2 3 6 1 5 4
// pivot==2: 2 (3 6 1 5 4)에서
// 왼쪽에서부터 2보다 큰 값을 찾는다. -> 3
// 오른쪽에서 2보다 작은 값을 찾는다. -> 1
// 둘의 위치를 바꾼다. -> 2 (1 6 3 5 4)
// 왼쪽에서부터 2보다 큰 값을 찾는다. -> 3
// 오른쪽에서 2보다 작은 값을 찾는다. -> 1
// 큰 값(3)의 인덱스 > 작은 값(1)의 인덱스 -> 작은 값과 pivot의 위치를 바꾼다. -> 1 {2} 6 3 5 4
// -> pivot이었던 2의 위치는 확정됐고, 2의 위치를 기준으로 왼쪽은 2보다 작은 값, 오른쪽은 큰 값이 된다.
// 2를 기준으로 나눠진 왼쪽과 오른쪽에 대해서도 퀵 정렬을 똑같이 진행한다.
// 왼쪽: 요소가 1개뿐이므로 그대로 둔다. -> {1 2} 6 3 5 4
// 오른쪽: pivot==6: {1 2} 6 (3 5 4)에서
// 왼쪽에서부터 6보다 큰 값을 찾는다. -> 없다. -> {1 2} 3 5 4 {6}
// 6의 왼쪽: pivot==3: {1 2} 3 (5 4) {6}
// 왼쪽에서부터 3보다 큰 값을 찾는다. -> 5
// 오른쪽에서부터 3보다 작은 값을 찾는다. -> 없다. -> {1 2 3} 5 4 {6}
// 3의 오른쪽: pivot==5: 요소가 2개뿐이므로 비교하면 5>4 -> {1 2 3 4 5 6}

2) partition()을 quicksort()로 옮긴 코드

// main()에서
int[] arr = {6, 3, 5, 9, 1, 10, 7, 2, 4, 8}; // 10개의 요소
quicksort(arr, 0, arr.length-1);

// 퀵 정렬 구현 메서드
static void quicksort(int[] arr, int start, int end) {
    if(start>=end) // 원소의 개수가 1개인 경우엔 정렬X
        return;
        
    int pivot = start; // 기준이 되는 pivot값의 위치
    int i = start+1, j = end, temp;
    // i에는 pivot보다 작은 값의 위치를, j에는 큰 값의 위치를 저장할 예정
    
    while(i<=j) { // pivot보다 작은 값의 위치와 큰 값의 위치가 엇갈릴 때까지 반복
        while(i<=end && arr[i]<=arr[pivot]) // 앞에서부터 pivot보다 큰 값을 찾음 
            i++;
        while(j>start && arr[j]>=arr[pivot]) // 뒤에서부터 pivot보다 작은 값을 찾음
            j--;
        if(i>j) { // pivot보다 작은 값 또는 큰 값이 없어서 엇갈리게 됐을 때
            temp = arr[j];
            arr[j] = arr[pivot];
            arr[pivot] = temp; // j번째가 pivot값의 위치로 확정짓게 된다.
        } else { // 엇갈리지 않았다면
            temp = arr[j];
            arr[j] = arr[i];
            arr[i] = temp; // i번째와 j번째의 값이 바뀌게 된다.
        }
    }
    
    // pivot값이 제자리를 찾았기 때문에
    // 그 왼쪽과 오른쪽을 나누어 퀵 정렬을 호출한다.
    quicksort(arr, start, j-1);
    quicksort(arr, j+1, end);
}

// main()에서 정렬 확인
for(int i : arr)
    System.out.print(i+","); // 1,2,3,4,5,6,7,8,9,10,

- 10개의 요소를 정렬할 때 O(n^2)을 따르는 정렬을 이용하면 총 100번의 비교 연산을 하게 된다.

- 퀵 정렬의 경우 10개의 요소를 (예를 들면) 5개/5개로 나눠서 비교하기 때문에 비교횟수가 5^2 * 2 = 50번을 하게 된다.

- 그러므로 시간 복잡도는 O(n*lgn)를 따른다.
- 대부분의 상황에서는 퀵 정렬이 빠른 편이지만, 이미 정렬이 되어있다면 퀵 정렬의 복잡도는 O(n^2)까지 나올 수 있다.