C++ 코딩테스트 강좌, 퀵 정렬

안녕하세요! 이번 시간에는 C++을 사용하여 퀵 정렬(Quick Sort) 알고리즘에 대해 자세히 살펴보겠습니다. 퀵 정렬은 다양한 프로그래밍 인터뷰와 알고리즘 시험에서 자주 등장하는 정렬 알고리즘입니다. 이 글에서는 퀵 정렬의 개념, 구현방법, 시간복잡도 및 예제문제를 통해 퀵 정렬을 마스터해보도록 하겠습니다.

1. 퀵 정렬 개요

퀵 정렬은 분할 정복 알고리즘의 일종으로, 데이터를 효율적으로 정렬하는 방법입니다. 이 알고리즘은 다음과 같은 방식으로 동작합니다:

주어진 배열에서 피벗(pivot) 요소를 선택합니다.
피벗을 기준으로 배열을 두 개의 부분 배열로 나눕니다.
(피벗보다 작은 요소들은 왼쪽 부분 배열에, 피벗보다 큰 요소들은 오른쪽 부분 배열에 위치하게 됩니다.)
왼쪽과 오른쪽 부분 배열 각각에 대해 퀵 정렬을 재귀적으로 수행합니다.
부분 배열이 정렬되면 피벗을 중간에 배치하여 최종 배열이 정렬됩니다.

1.1 피벗 선택

피벗 선택 방법은 여러 가지가 있습니다. 일반적인 방법으로는 다음과 같은 것들이 있습니다:

첫 번째 요소를 피벗으로 선택
마지막 요소를 피벗으로 선택
임의의 요소를 피벗으로 선택
중앙값을 피벗으로 선택

일반적으로 피벗 선택 방법이 정렬 성능에 큰 영향을 미치므로 적절한 방법을 선택하는 것이 중요합니다.

1.2 퀵 정렬의 시간 복잡도

퀵 정렬의 평균 시간 복잡도는 O(n log n)입니다. 그러나 최악의 경우(이미 정렬된 배열 등)에는 O(n²)로 성능이 저하될 수 있습니다. 이를 방지하기 위해 좋은 피벗 선택 방법이 중요합니다.

2. 문제 설명

이제 퀵 정렬을 활용한 문제를 풀어보겠습니다. 다음과 같은 문제를 해결해보세요.

문제: 정수 배열이 주어질 때, 퀵 정렬 알고리즘을 사용하여 배열을 오름차순으로 정렬하세요.
입력: [10, 7, 8, 9, 1, 5]
출력: [1, 5, 7, 8, 9, 10]

3. 문제 풀이 과정

문제 해결을 위한 단계는 다음과 같습니다:

3.1 알고리즘 구현

우선, 퀵 정렬 알고리즘을 C++로 구현해보겠습니다.

 
#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, 7, 8, 9, 1, 5};
    int n = arr.size();

    quickSort(arr, 0, n - 1);

    cout << "정렬된 배열: ";
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    return 0;
}

위 코드는 퀵 정렬 알고리즘의 구현입니다. partition 함수는 주어진 배열을 피벗을 기준으로 분할하고, quickSort 함수는 재귀적으로 정렬을 수행합니다.

3.2 코드 설명

코드를 단계별로 살펴보겠습니다:

partition 함수:
- 피벗으로 마지막 요소를 선택합니다.
- 주어진 배열을 피벗을 기준으로 분할합니다.
- 피벗을 정렬된 위치로 이동합니다.
- 새로운 피벗 인덱스를 반환합니다.
quickSort 함수:
- 기본 조건을 확인하여 부분 배열에 대해 재귀 호출합니다.
- 각 부분 배열에 대해 “피벗을 찾고, 정렬을 반복”하는 과정을 수행합니다.

3.3 코드 실행 결과

코드를 실행하면 다음과 같은 결과가 출력됩니다:

정렬된 배열: 1 5 7 8 9 10

정렬된 배열이 정상적으로 출력된 것을 확인할 수 있습니다. 이로써 퀵 정렬이 잘 수행되었음을 알 수 있습니다.

4. 추가적인 고려사항

퀵 정렬을 사용할 때 몇 가지 추가적인 고려사항이 있습니다:

4.1 안정성

퀵 정렬은 불안정 정렬 알고리즘입니다. 즉, 동일한 값을 가진 요소들의 상대적인 순서는 정렬 후 보장되지 않습니다. 만약 안정성이 필요한 경우, 다른 정렬 알고리즘(예: 병합 정렬)을 고려해야 합니다.

4.2 메모리 사용

퀵 정렬은 재귀적으로 동작하므로 호출 스택에 메모리를 사용합니다. 최악의 경우 O(n)의 공간 복잡도를 가질 수 있지만, 평균적으로는 O(log n)입니다.

5. 퀵 정렬 vs 다른 정렬 알고리즘

퀵 정렬은 다른 정렬 알고리즘들과 비교할 때 다음과 같은 장단점이 있습니다:

5.1 장점

평균적으로 O(n log n)의 빠른 성능을 보입니다.
추가적인 메모리 공간이 적게 필요합니다.
재귀적이고 직관적인 구현이 가능합니다.

5.2 단점

최악의 경우 O(n²)의 성능을 가질 수 있습니다.
불안정 정렬이며, 동일한 요소들의 상대적 순서가 바뀔 수 있습니다.

6. 결론

이번 글에서는 C++을 이용하여 퀵 정렬 알고리즘을 구현하고, 다양한 측면을 살펴보았습니다. 퀵 정렬은 효율적이고 널리 사용되는 정렬 알고리즘이므로, 알고리즘 시험 또는 코딩 면접에서 자주 다루어질 수 있습니다. 퀵 정렬을 이해하고 구현하는 것은 코딩 테스팅에 큰 도움이 될 것입니다.

마지막으로, 퀵 정렬을 활용하여 더 많은 문제를 풀어보세요. 다양한 경우의 수를 고려하는 것이 해당 알고리즘을 더 깊게 이해하는 데 도움이 될 것입니다.