퀵 정렬 (Quick Sort, 퀵 소트)

들어가며

퀵 정렬(Quick Sort) 알고리즘의 동작 과정을 시각적으로 표현

최근 모 기업의 필기 테스트에서 다뤄졌던 문제를 계기로 퀵 정렬에 대해 다시 공부하게 되었다. 퀵 정렬은 DB 인덱스처럼 여러 분야에서 중요한 역할을 하는 알고리즘으로, 효율성과 간결한 구조 덕분에 널리 사용된다.

본 글에서는 퀵 정렬의 기본 개념과 동작 원리, 그리고 특히 최악의 경우 발생 원인과 이를 개선하기 위한 최적화 전략을 단계적으로 살펴본다.

또한, 게임 개발, 3D 웹 애플리케이션, 모바일 게임 등 실시간 응용 프로그램에서 데이터 정렬의 효율성은 전체 시스템 성능에 큰 영향을 미치므로 이 알고리즘의 특성과 한계를 정확히 이해하는 것이 중요하다 생각한다.

---

퀵 정렬이란?

퀵 정렬은 분할 정복(Divide and Conquer) 알고리즘의 대표적인 예로, 배열이나 리스트와 같은 데이터 집합을 빠르게 정렬하는 효율적인 알고리즘이다.

기본 개념

퀵 정렬의 핵심 아이디어는 다음과 같다.

1. 피벗 선택
   배열에서 하나의 요소를 피벗(Pivot)으로 선택한다. 보통 배열의 첫 번째, 마지막 또는 랜덤하게 선택하며, 때로는 미디언-오브-쓰리(Median-of-Three) 기법을 사용해 보다 적절한 피벗을 고른다.
2. 분할(Partitioning)
   선택한 피벗을 기준으로 배열의 요소들을 두 그룹으로 나눈다.
   • 피벗보다 작은 요소는 왼쪽에,
   • 피벗보다 큰 요소는 오른쪽에 배치되고
   • 피벗은 최종 정렬 위치로 이동한다.
3. 재귀적 정렬(Recursive Sorting)
   피벗을 기준으로 나뉜 두 부분 배열에 대해 같은 과정을 재귀적으로 수행하여 전체 배열을 정렬한다.

퀵 정렬의 특징

• 효율성: 평균적으로 O(n log n)의 시간복잡도를 보이며, 대부분의 경우 매우 빠른 성능을 나타낸다.
• 제자리 정렬(In-place Sorting): 추가 메모리 없이 원본 배열 내에서 요소의 위치를 교환하며 정렬한다.
• 불안정 정렬(Unstable Sorting): 동일한 값을 가진 요소들의 상대적 순서를 보장하지 않는다.
• 분할 정복 전략: 문제를 작은 문제로 분할하여 해결함으로써 복잡한 문제도 쉽게 접근할 수 있다.

실무 적용 사례

• 게임 개발: Unity나 Unreal Engine 환경에서 렌더링 순서 조정, AI 우선순위 결정 등 다양한 상황에서 활용된다.
• 3D 웹 기술: React, Three.js 등으로 대규모 데이터를 실시간 처리할 때 유용하다.

---

퀵 정렬 알고리즘의 동작 원리

퀵 정렬은 피벗을 기준으로 배열을 분할한 후, 각 부분 배열에 대해 재귀적으로 정렬을 수행한다.

1. 분할(Partition) 과정

• 피벗 선택: 일반적으로 배열의 마지막 요소를 피벗으로 선택한다. (미디언-오브-쓰리 같은 기법도 사용 가능하다)
• 배열 분할: 피벗보다 작은 값은 왼쪽, 큰 값은 오른쪽으로 재배열하여 피벗을 최종 정렬 위치로 이동시킨다.

2. 재귀적 정복(Recursive Sorting)

• 재귀 호출: 분할된 두 부분 배열에 대해 같은 과정을 재귀적으로 수행한다.
• 기저 조건: 배열의 길이가 1 이하이면 정렬이 완료되었으므로 재귀를 종료한다.

3. 결합(Combine) 과정

퀵 정렬은 in-place 정렬 알고리즘이므로, 별도의 합병(merge) 과정 없이 분할과 정복만으로 전체 배열을 정렬한다.

C++ 예제 코드

#include <iostream>
#include <vector>
#include <algorithm> // std::swap 사용

using namespace std;

// Partition 함수: 배열을 피벗 기준으로 분할하고 피벗의 최종 인덱스를 반환한다.  
int partition(vector& 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& 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 arr = {9, 3, 7, 6, 2, 8, 5};
    quickSort(arr, 0, arr.size() - 1);

    for (int num : arr)
        cout << num << " ";
    cout << endl;

    return 0;
}

---

728x90

In-place 정렬이란?

In-place 정렬은 추가 메모리 없이 원본 배열 내에서 직접 요소의 위치를 변경하여 정렬하는 방식이다.

• 메모리 효율성: 추가 배열 없이 원본 데이터를 재배열하기 때문에 메모리 사용량이 적어 임베디드 시스템이나 모바일 환경에 유리하다.
• 빠른 데이터 접근 및 캐시 활용: 연속된 메모리 공간을 사용하므로 CPU 캐시 활용도가 높다.
• 퀵 정렬에서의 역할: 분할 단계에서 요소를 스왑하여 배열 내에서 직접 정렬하며, 별도의 병합 과정 없이 전체 배열이 정렬된다.

---

퀵 정렬의 시간복잡도

퀵 정렬은 피벗 선택과 분할의 균형 여부에 따라 시간복잡도가 달라진다.

1. 평균 및 최선의 경우: O(n log n)

• 설명: 무작위 데이터 또는 균형 잡힌 분할이 이루어지는 경우, 각 분할 단계에서 n번의 연산과 재귀 깊이 log n이 곱해져 평균적으로 O(n log n)의 시간복잡도를 갖는다.

2. 최악의 경우: O(n²)

• 설명 및 근거: 배열이 이미 정렬되어 있거나 역순일 때, 피벗이 항상 가장 작은 또는 가장 큰 값이 되면 한쪽에 n-1개, 그다음에는 n-2개… 식으로 분할되어 전체 비교 연산이 (n-1) + (n-2) + … + 1 ≈ n(n-1)/2가 되어 O(n²)가 된다.
• 예방 방법: 랜덤 피벗 선택이나 미디언-오브-쓰리 기법을 사용해 불균형 분할을 줄임으로써 최악의 경우를 방지할 수 있다.

3. 공간복잡도

• 재귀 호출 스택: 평균 O(log n)이며, 불균형 분할 시 최악에는 O(n)까지 증가할 수 있다.

---

퀵 정렬의 최악의 경우

퀵 정렬의 최악의 경우는 주로 피벗 선택에 의한 불균형 분할에서 발생한다.

발생 조건

• 불균형 분할: 매 분할 시 피벗이 배열에서 가장 작은 또는 큰 요소가 되어 한쪽에 모든 원소가 몰리게 되는 경우이다.
• 특정 데이터 패턴: 이미 정렬되어 있거나 역순인 배열에서 첫 번째 혹은 마지막 요소를 피벗으로 선택할 때 발생한다.

예시

예를 들어, [1, 2, 3, 4, 5]와 같이 오름차순으로 정렬된 배열에서 첫 번째 요소를 피벗으로 선택하면

• 첫 분할: 피벗 1, 오른쪽에 [2, 3, 4, 5]
• 두 번째 분할: 피벗 2, 오른쪽에 [3, 4, 5]
  와 같이 불균형 분할이 반복되어 전체 연산 횟수가 급증한다.

---

최악의 경우 개선 방법 및 최적화 전략

최악의 경우를 예방하기 위해 여러 최적화 전략을 도입한다.

1. 랜덤 피벗 선택

• 개념: 배열 내 임의의 위치에서 피벗을 선택해 데이터 순서에 따른 편향을 줄인다.
• 효과: 평균적으로 균형 잡힌 분할이 이루어져 최악의 경우(O(n²)) 발생 확률을 낮춘다.

2. 미디언-오브-쓰리

• 개념: 배열의 첫 번째, 중간, 마지막 요소 중 중간값을 피벗으로 선택한다.
• 효과: 이미 정렬된 배열 등 특정 패턴에서도 균형 잡힌 분할을 유도해 재귀 깊이를 줄인다.

3. 하이브리드 정렬

• 개념: 부분 배열의 크기가 작아지면 재귀 호출 대신 삽입 정렬(Insertion Sort) 등 간단한 정렬 알고리즘으로 전환한다.
• 효과: 작은 배열에서의 재귀 호출 오버헤드를 줄여 전체 성능을 개선한다.

4. 꼬리 재귀 최적화

• 개념 및 원리: 함수의 마지막에 자기 자신을 호출하는 꼬리 재귀는 컴파일러가 현재 스택 프레임을 재사용해 반복문으로 변환할 수 있다.
• 효과: 스택 메모리 사용을 줄여 재귀 깊이가 깊어지는 상황에서도 안정적인 실행을 보장한다.

5. Introsort

• 개념 및 원리: 초기에는 퀵 정렬을 사용하다가 재귀 깊이가 일정 임계치(일반적으로 log(n) 상수배)를 초과하면 힙 정렬(Heap Sort)로 전환하는 하이브리드 정렬 알고리즘이다.
• 효과: 퀵 정렬의 빠른 평균 성능과 힙 정렬의 최악의 경우 O(n log n) 성능 보장을 결합해 모든 데이터 패턴에서 안정적인 성능을 제공한다.
• 실제 적용: C++의 std::sort는 Introsort를 기반으로 구현되어 있다.

---

나가며

퀵 정렬은 평균적으로 매우 빠르고 효율적인 정렬 알고리즘(O(n log n))이지만, 피벗 선택에 따라 최악의 경우 O(n²)로 성능이 저하될 수 있다.

랜덤 피벗 선택, 미디언-오브-쓰리, 하이브리드 정렬, 꼬리 재귀 최적화, 그리고 Introsort와 같은 최적화 기법을 통해 이러한 최악의 경우를 예방하고 안정적인 성능을 유지할 수 있다.

이 글을 통해 퀵 정렬의 기본 원리, 시간복잡도, 최악의 경우 발생 원인 및 개선 전략을 학습해 두면, 알고리즘 설계와 최적화에 대한 깊은 이해를 갖게 되고, 기술 면접이나 실무 개발에서 큰 도움이 될 것이다.

---

참고 자료

• Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.)
  알고리즘 전반에 걸친 이론과 정렬 알고리즘 분석을 다룬다.
• Musser, D. R. (1997). Introsort — a hybrid sorting algorithm. Software: Practice and Experience, 27(8), 983-993.
  Introsort의 개념과 구현 방법을 설명한다.
• Wikipedia - Quick Sort
  퀵 정렬의 기본 원리 및 피벗 선택 기법을 자세히 설명한다.
• GeeksforGeeks - Quick Sort Algorithm
  다양한 피벗 선택 및 최적화 전략에 관한 예제와 설명을 제공한다.
• C++ Reference - std::sort
  C++ 표준 라이브러리의 정렬 함수 구현 설명을 확인할 수 있다.
• Unity Performance Optimization 및 Unreal Engine Optimization Guidelines
  게임 개발 환경에서 성능 최적화 사례와 권장 사항을 제공한다.