정렬 - 퀵정렬(Quick Sort)

퀵정렬(Quick Sort)

 

오늘은 퀵정렬에 대해 알아보겠습니다. 퀵정렬은 "대표적인 분할정복 알고리즘으로 평균속도가 O(nlogn)" 입니다.

#include <iostream>
#include <vector>

using namespace std;

// 배열을 분할하는 함수
int partition(vector<int>& arr, int low, int high) {
    int pivot = arr[high]; // 피벗을 마지막 요소로 설정
    int i = low - 1; // 작은 요소들의 인덱스

    for (int j = low; j < high; j++) {
        if (arr[j] < pivot) { // 피벗보다 작은 경우
            i++;
            swap(arr[i], arr[j]);
        }
    }
    swap(arr[i + 1], arr[high]); // 피벗을 올바른 위치로 이동
    return i + 1;
}

// 퀵정렬 함수
void quickSort(vector<int>& arr, int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

int main() {
    vector<int> arr = {10, 3, 8, 9, 1, 5};
    int n = arr.size();

    cout << "정렬 전 배열: ";
    for (int num : arr) cout << num << " ";
    cout << endl;

    quickSort(arr, 0, n - 1);

    cout << "정렬 후 배열: ";
    for (int num : arr) cout << num << " ";
    cout << endl;

    return 0;
}

 

퀵정렬은 평균적으로 수행시간이 빠른 방법으로 많이 쓰입니다. 분할정복 기법을 기반으로 사용되며, 피벗을 중심으로 하는 재귀적 구조가 특징입니다.

 

이제 퀵정렬의 동작과정을 살펴보겠습니다.

 

1. 피벗(Pivot) 선택 : 리스트에서 기준이 되는 하나의 요소(피벗)를 선택합니다.

2. 피벗을 기준으로 분할 : 피벗보다 작은 값들은 왼쪽, 큰 값들은 오른쪽으로 나눕니다.

3. 재귀적 정렬 : 나눈 두 개의 리스트(피벗보다 작은 값들의 리스트, 피벗보다 큰 값들의 리스트)에 대해 같은 과정을 재귀적으로 반복합니다.

4. 병합 : 각 분할이 완료되면 병합 과정 없이 리스트가 완성됩니다.

 

이제 이 과정을 예시로 설명하겠습니다. [10, 3, 8, 9, 1, 5]를 오름차순 퀵정렬할 때, 첫번째로 피벗을 선택합니다. 리스트의 마지막 요소인 5를 피벗으로 해보겠습니다. 이후 피벗을 기준으로 분할합니다. 5보다 작은 건 왼쪽, 큰건 오른쪽으로 이동합니다. 모양을 나타내면 [3, 1] | 5 | [10, 8, 9] 이 됩니다. 이제 왼쪽과 오른쪽에 대해 다시 퀵정렬을 적용합니다. 왼쪽 마지막 요소 1을 기준으로 하면, | 1 | [3]이 되고, 오른쪽도 마지막 요소 9를 기준으로 하면 [8] | 9 | [10]이 됩니다. 이 과정을 오름차순 정렬이 될 때까지 재귀적으로 반복하여 최종적으로 [1, 3, 5, 8, 9, 10]이 완성됩니다.

 

퀵정렬의 특징

시간복잡도 : O(nlogn)

=> 최악의 경우(피벗 선택이 매우 비효율적인 경우) : O(n^2)

=> 최선의 경우(리스트가 이미 정렬된 경우) : O(nlogn)

=> 평균 : O(nlogn)

 

공간복잡도 : O(logn)

=> 퀵정렬은 제자리 정렬로 별도의 추가 메모리 공간을 거의 사용하지 않습니다. 하지만 재귀 호출이 사용되므로, 재귀 호출 스택 깊이에 따라 추가 메모리가 필요합니다.

 

안정성 : 불안정정렬

=> 같은 값을 가진 요소들의 순서는 정렬 후에 바뀔 수 있습니다. 원소를 분할하고 교환하는 과정에서 동일 값을 가진 원소들이 서로 자리를 바꾸기 때문입니다.

 

장단점

장점

- 빠른 평균 성능

- 제자리 정렬

- 분할 정복 방식

 

단점

- 최악의 경우 성능

- 불안정성

- 재귀 호출

 

퀵정렬의 피벗 선택 방법

퀵 정렬의 성능은 피벗 선택 방법에 크게 의존합니다. 즉, 피벗을 잘 선택하면 성능이 크게 향상됩니다.

- 첫 번째 원소 : 가장 간단한 방법으로, 리스트의 첫 번째 원소를 피벗으로 선택합니다. 하지만 리스트가 이미 정렬되어 있을 경우 비효율적입니다.

- 마지막 원소 : 리스트의 마지막 원소를 피벗으로 선택하는 방법도 있습니다. 하지만 이 역시 리스트가 정렬되어 있거나 역순일 때 성능이 떨어집니다.

- 랜덤 피벗 : 리스트에서 무작위로 피벗을 선택하는 방법입니다. 평균적인 성능이 좋아지는 경향이 있습니다.

- 중간값 피벗(Median-of-Three) : 첫 번째 원소, 중간 원소, 마지막 원소 중에서 중간값을 피벗으로 선택하는 방식입니다. 이는 균형 잡힌 분할을 유도할 가능성이 높습니다.

 

퀵정렬의 활용

퀵정렬은 대체적으로 다른 알고리즘에 비해 빠른 속도를 가지고 있으며, 최악의 경우에는 성능이 좋지 않지만, 최악의 경우는 실제로 잘 발생하지 않습니다. 그리고 실제 응용에서 매우 빠른 속도를 보이는 이유는 캐시 친화적인 메모리 접근 패턴과 낮은 상수 계수 때문입니다.

 

캐시 친화적 : 퀵정렬은 배열의 연속된 메모리 위치를 탐색하기 때문에, 메모리 캐시를 효과적으로 활용합니다. 이는 실제 실행 시 성능을 크게 개선시킵니다.

낮은 상수 계수 : 퀵정렬은 비교적 간단한 교환 작업과 비교 작업을 사용하여 정렬을 수행하므로, 실행 시간에 큰 상수 계수를 추가하지 않습니다. 따라서 O(nlogn) 성능을 보이는 다른 알고리즘(ex : 병합정렬)보다 실제로 빠르게 작동하는 경우가 많습니다.

 

실제로 대부분의 경우에서 퀵정렬은 병합정렬이나 힙정렬보다 더 빠르게 작동하며, 이는 퀵정렬이 많은 프로그래밍 언어나 라이브러리에서 기본 정렬 알고리즘으로 채택되는 이유 중 하나입니다.

 

NEXT

오늘은 퀵정렬에 대해 알아보았습니다. 이전에 알아보았던 알고리즘 중 가장 빠른 속도와 보편적인 활용성을 자랑하며, 분할정복 방식과 재귀적 호출을 사용하는 알고리즘입니다. 빠른 만큼 대부분의 문제 해결 및 기본 정렬 알고리즘으로 채택되어 사용되므로 알아두면 좋을 것 같습니다. 다음은 정렬의 마지막으로 합병정렬에 대해 알아보겠습니다. 감사합니다.