본 시리즈는 프로그래밍 알고리즘의 개념을 정리하고 실습을 진행해보는 시리즈입니다.

• 실습은 다음과 같은 개발환경 및 버전에서 진행하였습니다.
  • IDE : IntelliJ IDEA (Ultimate Edition)
  • Java : JDK 21 (corretto-21)
  • Python : 3.9 (conda env)

[알고리즘] 정렬(Sorting) - Quick Sort & Dual-Pivot Quick Sort

• 정렬 알고리즘의 전반적인 개요와 분류는 다음 포스팅에서 확인하실 수 있습니다.
  • [알고리즘] 정렬(Sorting) - 개요 (Java와 Python의 주요 정렬 방식 소개)

1. 분할 정복 기반 정렬 (Divide and Conquer)

분할 정복 기반 정렬 알고리즘은 문제를 작은 부분으로 나누고, 각각을 정렬한 후 다시 합쳐 전체 문제를 해결하는 방식입니다.

• 이러한 방식은 대규모 데이터에서 효율적이며, 성능 면에서 매우 우수합니다.
• 대표적인 알고리즘으로는 퀵 정렬, 듀얼 피벗 퀵 정렬, 합병 정렬, 그리고 팀 정렬이 있습니다.

이번 포스팅에서는 퀵 정렬, 듀얼 피벗 퀵 정렬을 다루고, 다음 포스팅에서 합병 정렬과 팀 정렬을 다룹니다.

2. 퀵 정렬 (Quick Sort)

2.1 Quick Sort란?

퀵 정렬 (Quick Sort)은 분할 정복 (Divide and Conquer) 기법을 사용하여 배열을 정렬하는 알고리즘입니다.

• 피벗(pivot)이라 불리는 기준 값을 선택하고, 피벗을 기준으로 작은 값은 왼쪽에, 큰 값은 오른쪽에 배치하는 과정을 반복하여 배열을 정렬합니다.
• 퀵 정렬은 평균적으로 매우 빠른 성능을 보이는 정렬 알고리즘으로, 평균 시간 복잡도는 $O(n \log n)$입니다.

퀵 정렬의 주요 특징:

• 제자리 정렬 (in-place sorting): 추가 메모리를 거의 사용하지 않습니다.
• 불안정 정렬 (unstable sort): 동일한 값을 가진 요소들의 상대적인 순서가 유지되지 않습니다.
• 최악의 경우: 피벗 선택이 잘못되면 $O(n^2)$의 시간 복잡도를 가질 수 있습니다.

2.2 Quick Sort 동작 원리

퀵 정렬은 세 단계로 이루어집니다:

1. 피벗 선택:
   • 배열에서 피벗을 선택합니다.
   • 일반적으로 첫 번째, 마지막 또는 중간 값을 피벗으로 선택하지만, 랜덤하게 선택하는 방법도 사용됩니다.
2. 분할 과정:
   • 피벗을 기준으로 배열을 두 부분으로 나눕니다.
   • 피벗보다 작은 값은 왼쪽으로, 큰 값은 오른쪽으로 배치합니다.
3. 재귀 호출:
   • 피벗을 기준으로 나뉜 왼쪽 부분과 오른쪽 부분에 대해 퀵 정렬을 재귀적으로 반복합니다.

동작 예시:
주어진 배열 [5, 2, 1, 9, 4]을 퀵 정렬로 정렬하는 과정:

1. 피벗 선택: 4를 피벗으로 선택합니다.
2. 분할: 피벗 4를 기준으로 작은 값은 왼쪽, 큰 값은 오른쪽으로 나누면 [2, 1] | 4 | [5, 9]가 됩니다.
3. 재귀 호출:
   • 왼쪽 부분 [2, 1]에 대해 퀵 정렬을 수행:
     • 1을 피벗으로 선택, [1] | 2로 정렬 완료.
   • 오른쪽 부분 [5, 9]에 대해 퀵 정렬을 수행:
     • 9을 피벗으로 선택, [5] | 9로 정렬 완료.
4. 최종 결과: [1, 2, 4, 5, 9]으로 정렬됩니다.

2.3 Quick Sort 구현 (Java)

import java.util.Arrays;

public class QuickSort {
    // 퀵 정렬 메서드
    public static void quickSort(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);
        }
    }

    // 배열을 분할하는 메서드
    public static int partition(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++;
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }

        // 피벗을 적절한 위치로 이동
        int temp = arr[i + 1];
        arr[i + 1] = arr[high];
        arr[high] = temp;

        return i + 1;
    }

    public static void main(String[] args) {
        int[] arr = {9, 2, 1, 5, 4};
        quickSort(arr, 0, arr.length - 1);
        System.out.println("Sorted array: " + Arrays.toString(arr));
    }
}

Java 구현 설명:

• partition 메서드는 배열을 분할하고, 피벗을 적절한 위치에 놓습니다.
• quickSort 메서드는 분할된 배열의 좌측과 우측 부분에 대해 재귀적으로 정렬을 수행합니다.

출력 예시:

Sorted array: [1, 2, 4, 5, 9]

2.4 Quick Sort 구현 (Python)

def quick_sort(arr, low, high):
    if low < high:
        # 분할 지점
        pi = partition(arr, low, high)

        # 좌측과 우측 파티션에 대해 재귀적으로 정렬 수행
        quick_sort(arr, low, pi - 1)
        quick_sort(arr, pi + 1, high)

def partition(arr, low, high):
    pivot = arr[high]  # 마지막 요소를 피벗으로 선택
    i = low - 1  # 작은 요소의 인덱스

    for j in range(low, high):
        if arr[j] < pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]  # 교환

    arr[i + 1], arr[high] = arr[high], arr[i + 1]  # 피벗을 적절한 위치로 이동
    return i + 1

# 예시 배열
arr = [9, 2, 1, 5, 4]
quick_sort(arr, 0, len(arr) - 1)
print("Sorted array:", arr)

Python 구현 설명:

• partition 함수는 피벗을 기준으로 배열을 분할합니다.
• quick_sort 함수는 분할된 배열의 좌측과 우측 부분에 대해 재귀적으로 정렬을 수행합니다.

출력 예시:

Sorted array: [1, 2, 4, 5, 9]

3. 듀얼 피벗 퀵 정렬 (Dual-Pivot Quick Sort)

3.1 Dual-Pivot Quick Sort란?

Dual-Pivot Quick Sort는 퀵 정렬(Quick Sort)의 변형된 알고리즘으로, 두 개의 피벗을 사용하여 배열을 세 부분으로 나누어 정렬하는 방식입니다.

• 일반 퀵 정렬은 하나의 피벗을 사용해 배열을 두 부분으로 나누지만, 듀얼 피벗 퀵 정렬은 두 개의 피벗을 선택하여 세 개의 부분으로 분할합니다:
  • 첫 번째 부분: 피벗1보다 작은 값들
  • 두 번째 부분: 피벗1과 피벗2 사이의 값들
  • 세 번째 부분: 피벗2보다 큰 값들

이 알고리즘은 비교 횟수를 줄일 수 있어 일반적인 퀵 정렬보다 더 효율적일 수 있으며, 특히 Java의 Arrays.sort() 메서드에서 대규모 기본형 배열을 정렬할 때 사용됩니다.

시간 복잡도:

• 평균: $O(n \log n)$
• 최악: $O(n^2)$ (잘못된 피벗 선택 시)

특징:

• 퀵 정렬보다 비교 횟수를 줄일 수 있음
• Java 7부터 기본형 배열에서 주요 정렬 알고리즘으로 사용됨

3.2 Dual-Pivot Quick Sort 동작 원리

Dual-Pivot Quick Sort는 다음과 같은 단계로 동작합니다:

1. 두 개의 피벗 선택:
   • 배열에서 두 개의 피벗을 선택합니다. 일반적으로 첫 번째와 마지막 요소가 피벗으로 선택됩니다.
2. 세 부분으로 분할:
   • 피벗1보다 작은 값들은 왼쪽으로 이동.
   • 피벗1과 피벗2 사이의 값들은 중간에 위치.
   • 피벗2보다 큰 값들은 오른쪽으로 이동.
3. 재귀적으로 정렬:
   • 세 부분으로 나눈 각 구간에 대해 재귀적으로 Dual-Pivot Quick Sort를 적용합니다.
4. 최종 배열은 피벗1과 피벗2를 기준으로 정렬된 세 구간이 합쳐지며 완료됩니다.

동작 예시:
주어진 배열 [2, 9, 1, 5, 4, 7, 8, 3, 6]을 듀얼 피벗 퀵 정렬로 정렬하는 과정:

1. 피벗 선택: 배열의 첫 번째 요소 2와 마지막 요소 6을 두 개의 피벗으로 선택합니다.

   • 피벗1: 2
   • 피벗2: 6

2. 세 부분으로 분할:

   • 피벗1(2)보다 작은 값은 왼쪽으로 이동: [1]
   • 피벗1(2)와 피벗2(6) 사이의 값은 중간에 위치: [5, 4, 3]
   • 피벗2(6)보다 큰 값은 오른쪽으로 이동: [9, 7, 8]
   • 분할 결과: [1] | [2] | [5, 4, 3] | [6] | [9, 7, 8]

3. 재귀적으로 정렬:

   • 왼쪽 [1]과 피벗1 [2]은 이미 정렬된 상태이므로 더 이상 정렬하지 않습니다.
   • 중간 구간 [5, 4, 3]에 대해 Dual-Pivot Quick Sort를 다시 적용:
     • 피벗1: 3, 피벗2: 5
     • 분할 결과: [4]는 3과 5 사이에 위치하며 재귀적으로 정렬이 완료됩니다.
   • 오른쪽 구간 [9, 7, 8]에 대해 재귀적으로 Dual-Pivot Quick Sort 적용:
     • 피벗1: 7, 피벗2: 9
     • 분할 결과: [8]은 7과 9 사이에 위치하며 재귀적으로 정렬이 완료됩니다.

4. 최종 정렬 결과: 모든 부분을 정렬하고 합치면 배열은 [1, 2, 3, 4, 5, 6, 7, 8, 9]으로 정렬됩니다.

3.3 Dual-Pivot Quick Sort 구현 (Java)

import java.util.Arrays;

public class DualPivotQuickSort {
    // Dual-Pivot Quick Sort 구현
    public static void dualPivotQuickSort(int[] arr, int low, int high) {
        if (low < high) {
            // 두 개의 피벗을 선택
            int[] pivots = partition(arr, low, high);
            int pivot1 = pivots[0];
            int pivot2 = pivots[1];

            // 피벗1보다 작은 부분, 피벗1과 피벗2 사이의 부분, 피벗2보다 큰 부분 각각 정렬
            dualPivotQuickSort(arr, low, pivot1 - 1);
            dualPivotQuickSort(arr, pivot1 + 1, pivot2 - 1);
            dualPivotQuickSort(arr, pivot2 + 1, high);
        }
    }

    // 피벗으로 배열을 세 구간으로 분할하는 함수
    private static int[] partition(int[] arr, int low, int high) {
        if (arr[low] > arr[high]) {
            swap(arr, low, high); // 피벗1과 피벗2를 정렬
        }
        int pivot1 = arr[low];
        int pivot2 = arr[high];

        int i = low + 1;
        int j = low + 1;
        int k = high - 1;

        while (j <= k) {
            if (arr[j] < pivot1) {
                swap(arr, i++, j++);
            } else if (arr[j] > pivot2) {
                swap(arr, j, k--);
            } else {
                j++;
            }
        }
        swap(arr, low, --i);   // 피벗1을 제자리에 놓음
        swap(arr, high, ++k);  // 피벗2를 제자리에 놓음

        return new int[]{i, k}; // 피벗1과 피벗2의 위치 반환
    }

    // 배열 요소 교환 함수
    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void main(String[] args) {
        int[] arr = {2, 9, 1, 5, 4, 7, 8, 3, 6};
        dualPivotQuickSort(arr, 0, arr.length - 1);
        System.out.println("Sorted array: " + Arrays.toString(arr));
    }
}

Java 구현 설명:

• dualPivotQuickSort는 두 개의 피벗을 사용해 배열을 세 부분으로 나누고, 이를 재귀적으로 정렬하는 Dual-Pivot Quick Sort 알고리즘을 구현합니다.
• partition 함수는 피벗1, 피벗2를 선택하고, 배열을 세 구간으로 분할합니다. 이후 피벗1과 피벗2를 각 구간에 배치하고 그 사이 부분을 다시 정렬합니다.
• 이 구현은 Java에서 큰 크기의 기본형 배열을 정렬하는데 사용되는 Dual-Pivot Quick Sort의 구조를 단순화하여 구현하였습니다.

출력 예시:

Sorted array: [1, 2, 3, 4, 5, 6, 7, 8, 9]

3.4 Dual-Pivot Quick Sort 구현 (Python)

# 배열 요소 교환 함수
def swap(arr, i, j):
    arr[i], arr[j] = arr[j], arr[i]

# 배열을 두 개의 피벗을 기준으로 세 구간으로 나누는 함수
def partition(arr, low, high):
    if arr[low] > arr[high]:
        swap(arr, low, high)  # 피벗1과 피벗2를 정렬
    pivot1 = arr[low]
    pivot2 = arr[high]

    i = low + 1
    j = low + 1
    k = high - 1

    while j <= k:
        if arr[j] < pivot1:
            swap(arr, i, j)
            i += 1
            j += 1
        elif arr[j] > pivot2:
            swap(arr, j, k)
            k -= 1
        else:
            j += 1  # 피벗 사이의 값에 대해 j 증가
    swap(arr, low, i - 1)   # 피벗1을 제자리에 놓음
    swap(arr, high, k + 1)  # 피벗2를 제자리에 놓음

    return i - 1, k + 1  # 피벗1과 피벗2의 위치 반환

# Dual-Pivot Quick Sort 구현
def dual_pivot_quick_sort(arr, low, high):
    if low < high:
        pivot1, pivot2 = partition(arr, low, high)
        
        # 피벗1보다 작은 부분, 피벗1과 피벗2 사이의 부분, 피벗2보다 큰 부분 각각 정렬
        dual_pivot_quick_sort(arr, low, pivot1 - 1)
        dual_pivot_quick_sort(arr, pivot1 + 1, pivot2 - 1)
        dual_pivot_quick_sort(arr, pivot2 + 1, high)

# 예시 배열
arr = [2, 9, 1, 5, 4, 7, 8, 3, 6]
dual_pivot_quick_sort(arr, 0, len(arr) - 1)
print("Sorted array:", arr)

Python 구현 설명:

• dual_pivot_quick_sort는 두 개의 피벗을 기준으로 배열을 세 부분으로 나누어 재귀적으로 정렬하는 알고리즘입니다.
• partition 함수는 배열을 세 구간으로 나누고, 피벗을 각각의 자리에 배치한 후, 피벗을 기준으로 세 부분을 재귀적으로 정렬합니다.

출력 예시:

Sorted array: [1, 2, 3, 4, 5, 6, 7, 8, 9]

4. 분할 정복 기반 정렬 알고리즘 복잡도

분할 정복 기반 정렬 알고리즘들은 문제를 작은 단위로 분할한 후 각각을 정렬하고 다시 합쳐 전체 문제를 해결하는 방식입니다.

• 이 방식은 대규모 데이터에서 매우 효율적이며, 대표적으로 퀵 정렬(Quick Sort), 듀얼 피벗 퀵 정렬(Dual-Pivot Quick Sort), 합병 정렬(Merge Sort), 그리고 팀 정렬(Tim Sort) 등이 있습니다.

다음은 각 정렬 알고리즘의 시간 복잡도와 특징을 비교하여 정리한 표입니다.

정렬 알고리즘	평균 시간 복잡도	최악 시간 복잡도	공간 복잡도	안정성	특징
Quick Sort	$O(n \log n)$	$O(n^2)$	$O(\log n)$	불안정	피벗 선택에 따라 최악의 성능을 가짐 (불균형 분할의 경우)
Dual-Pivot Quick Sort	$O(n \log n)$	$O(n \log n)$	$O(\log n)$	불안정	두 피벗을 사용하여 성능을 개선한 퀵 정렬
Merge Sort	$O(n \log n)$	$O(n \log n)$	$O(n)$	안정적	재귀 호출로 인해 추가 메모리 사용, 안정적 정렬 보장
Tim Sort	$O(n \log n)$	$O(n \log n)$	$O(n)$	안정적	실무에서 자주 사용되며, Java와 Python의 기본 정렬 알고리즘

4.1 시간 복잡도 설명

1. Quick Sort:

   • 평균 시간 복잡도는 $O(n \log n)$으로 매우 효율적이나, 피벗이 적절하지 않게 선택되는 경우 (예: 매번 가장 작은 혹은 가장 큰 값이 피벗으로 선택되는 경우) 최악의 시간 복잡도가 $O(n^2)$로 떨어질 수 있습니다.
   • 공간 복잡도는 스택 공간만 사용하므로 $O(\log n)$입니다.
   • 퀵 정렬은 불안정 정렬입니다. 즉, 같은 값을 가진 데이터의 상대적인 순서가 유지되지 않습니다.

2. Dual-Pivot Quick Sort:

   • 두 개의 피벗을 사용하여 배열을 세 부분으로 나누는 듀얼 피벗 퀵 정렬은, 전통적인 퀵 정렬보다 비교 횟수를 줄여 성능을 개선합니다.
   • Java의 기본형 배열에서 사용되는 방식으로, 대규모 데이터셋에서 뛰어난 성능을 발휘합니다.
   • 최악의 경우에도 $O(n \log n)$을 보장하지만, 불안정 정렬입니다.

3. Merge Sort:

   • 항상 $O(n \log n)$의 시간 복잡도를 보장하는 안정적 정렬 알고리즘입니다.
   • 다만 재귀 호출과 병합 과정에서 추가 메모리가 필요하므로, 공간 복잡도가 $O(n)$입니다.
   • 특히 데이터가 이미 정렬된 상태에서도 동일한 성능을 유지하기 때문에 안정 정렬이 필요할 때 유용합니다.

4. Tim Sort:

   • Merge Sort와 Insertion Sort를 결합한 하이브리드 정렬 알고리즘으로, 부분적으로 정렬된 데이터를 효율적으로 처리합니다.
   • Python과 Java의 표준 정렬 알고리즘으로 사용되며, 실제 상황에서 매우 효율적입니다. 최선의 경우 $O(n)$의 성능을 보일 수 있으며, 안정적인 정렬을 보장합니다.
   • 삽입 정렬을 활용해 작은 배열을 처리하고, 나머지를 병합 정렬로 처리하는 방식입니다.

4.2 결론

분할 정복 기반 정렬 알고리즘은 대부분 $O(n \log n)$의 시간 복잡도를 가지며, 데이터 특성에 따라 선택해야 합니다.

• Quick Sort와 Dual-Pivot Quick Sort는 메모리 사용량이 적고 빠르지만 안정성을 보장하지 않으며, 최악의 경우 성능이 저하될 수 있습니다.
• Merge Sort와 Tim Sort는 안정적 정렬을 필요로 할 때 유리하지만, 추가 메모리 사용이 필요하여 제한된 메모리 환경에서는 주의해야합니다.

마무리

이번 포스팅에서는 퀵 정렬과 듀얼 피벗 퀵 정렬의 기본 개념과 동작 원리, 그리고 구현을 다루었습니다.

• 두 알고리즘은 빠른 평균 성능을 자랑하지만, 피벗 선택에 따라 성능이 달라질 수 있다는 점에서 주의가 필요합니다.

다음 포스팅에서는 합병 정렬(Merge Sort)과 팀 정렬(Tim Sort)을 다루며, 이들의 구체적인 동작 방식과 구현 방법을 소개할 예정입니다.