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

숭실대학교 컴퓨터학부의 알고리즘 수업을 들으며 정리한 내용입니다.
참고교재: 쉽게 배우는 알고리즘(문병로)

기본적인 정렬 알고리즘 O(n^2)
1.선택정렬
2.버블정렬
3.삽입정렬

고급 정렬 알고리즘 O(n*logn)
1.병합정렬
2.퀵정렬
3.힙정렬

특수 정렬 알고리즘 O(n)
1.계수정렬
2.기수정렬

퀵정렬이란

퀵 정렬(Quick Sort)은 분할 정복 방식의 효율적인 정렬 알고리즘 중 하나입니다. 퀵 정렬은 배열을 두 부분으로 분할하고, 각 부분을 재귀적으로 정렬하여 전체 배열을 정렬합니다. 분할 시 기준이 되는 '피벗'을 선택하고, 피벗보다 작은 요소는 왼쪽, 큰 요소는 오른쪽으로 이동합니다.

pivot을 기준으로 퀵저열이 실행되는 모습, 출처:위키백과

 

퀵 정렬의 시간 복잡도는 평균적으로 O(n log n)입니다. 하지만 최악의 경우(이미 정렬된 배열 등) O(n^2)이 될 수 있으므로, 이 점을 주의해야 합니다.

 

퀵정렬 코드

void quickSort(int A[], int low, int high) {
    if(low >= high) return;

    int i = low, j = low;
    int&pivot = A[high];
    for (; j < high; ++j) {
        if ( A[j] < pivot)
            swap(A[i++], A[j]);
    }
    swap(A[i], pivot);

    quickSort(A, low, i-1);
    quickSort(A, i+1, high);
}

 

테스트 코드

int main() {
    int arr[] = {20, 30,10,21,5,39,2};
    int arr_size = sizeof(arr)/sizeof(arr[0]);

    cout << "Given array is \n";
    for (int i=0; i < arr_size; i++)
        cout << arr[i] << " ";

    quickSort(arr, 0, arr_size - 1);

    cout << "\nSorted array is \n";
    for (int i=0; i < arr_size; i++)
        cout << arr[i] << " ";

    return 0;
}

테스트 결과

Given array is
20 30 10 21 5 39 2
Sorted array is
2 5 10 20 21 30 39