[정렬] 퀵 정렬(Quick Sort)

- 정렬할 배열에서 "기준 원소"를 하나 고른다.

- 이 기준 원소를 중심으로 더 작거나 같은 수는 왼쪽으로, 큰 수는 오른쪽으로 배치한다.

  (기준 원소는 분할된 양쪽 부분 배열 사이에 자리하게 된다.)

- 이렇게 분열된 왼쪽 부분과 오른쪽 배열을 따로 정렬한다.

- 여기서 왼쪽과 오른쪽 부분 배열을 정렬할 때, 퀵 정렬을 재귀적으로 사용한다.

 

 

다음은 퀵 정렬 알고리즘이다.

quickSort(A[], p, r) { // A[p...r]을 정렬한다
    if(p<r) then {
        q = partition(A, p, r);    // 분할
        quickSort(A, p, q-1);    // 왼쪽 부분배열 정렬
        quickSort(A, q+1, r);    // 오른쪽 부분배열 정렬
    }
}

partition(A[], p, r) {
    배열 A[p...r]의 원소들을 A[r]을 기준으로 양쪽으로 재배치하고
    A[r]이 자리한 위치를 return
}

 

partition 함수를 더 자세히 풀어서 보자

partition(A[], p, r){
    x ← A[r];
    i ← p-1;
    for j ← p to r-1
        if(A[j] <= x) then A[++i] ↔ A[j];
    A[i+1] ↔ A[r];
    return i+1;
}

 

 

따라서,

 

최선의 경우는 항상 절반으로 분할되는 경우로 시간 복잡도는 O(n log n)이 된다.

 

 

최악의 경우는 반대로 항상 절반으로 분할되지 않을 경우로 시간 복잡도는 O(n^2)이 된다.