퀵 정렬(Quick Sort)

 

 

 

1. 퀵 정렬이란?

퀵 정렬(Quick Sort)은 분할 정복(Divide and Conquer) 알고리즘을 기반으로 한 정렬 방식으로, 피벗(Pivot)을 선택하여 작은 값과 큰 값으로 배열을 나눈 뒤 정렬하는 방식입니다.

퀵 정렬은 평균적으로 **O(n log n)**의 시간 복잡도를 가지며, 빠른 정렬 성능을 제공하는 대표적인 정렬 알고리즘 중 하나입니다.

2. 퀵 정렬 동작 원리

퀵 정렬은 다음과 같은 방식으로 동작합니다:

1. 배열에서 하나의 요소를 **피벗(Pivot)**으로 선택합니다.
2. 피벗을 기준으로 작은 값은 왼쪽, 큰 값은 오른쪽으로 배치합니다.
3. 분할된 두 개의 부분 배열에 대해 재귀적으로 퀵 정렬을 수행합니다.
4. 모든 요소가 정렬될 때까지 이 과정을 반복합니다.

예제: 퀵 정렬 과정 (오름차순 정렬)

다음과 같은 배열이 있다고 가정하겠습니다.

[5, 3, 8, 4, 2]

퀵 정렬이 진행되는 과정은 다음과 같습니다.

1. 피벗 선택 (예: 마지막 요소 선택) → pivot = 2
2. 피벗을 기준으로 분할 → [ ] 2 [5, 3, 8, 4]
3. 좌측과 우측 부분 배열을 다시 퀵 정렬 수행
   • [5, 3, 8, 4]에서 pivot = 4
   • [3] 4 [5, 8]
   • [5, 8]에서 pivot = 8
   • [5] 8 [ ]
4. 최종 정렬된 결과 → [2, 3, 4, 5, 8]

3. 퀵 정렬 코드

public class QuickSort {
    public static void quickSort(int[] arr, int left, int right) {
        if (left < right) {
            int pivotIndex = partition(arr, left, right);
            quickSort(arr, left, pivotIndex - 1);
            quickSort(arr, pivotIndex + 1, right);
        }
    }

    private static int partition(int[] arr, int left, int right) {
        int pivot = arr[right];
        int i = left - 1;
        
        for (int j = left; j < right; j++) {
            if (arr[j] < pivot) {
                i++;
                swap(arr, i, j);
            }
        }
        swap(arr, i + 1, right);
        return i + 1;
    }

    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 = {5, 3, 8, 4, 2};
        quickSort(arr, 0, arr.length - 1);
        
        for (int num : arr) {
            System.out.print(num + " ");
        }
        // 출력: 2 3 4 5 8
    }
}

4. 퀵 정렬의 시간 복잡도

경우	시간 복잡도
최선의 경우	O(n log n)
평균의 경우	O(n log n)
최악의 경우	O(n²) (이미 정렬된 경우)

• 분할 과정에서 O(log n) 단계가 필요하고, 각 단계에서 O(n) 연산이 이루어짐
• 따라서 전체 시간 복잡도는 O(n log n) (단, 피벗 선택이 좋지 않으면 O(n²)까지 증가할 수 있음)

5. 퀵 정렬의 장점과 단점

✅ 장점

• 빠른 평균 시간 복잡도 O(n log n)
• 제자리 정렬(In-place Sort)로 메모리 사용이 적음
• 분할 정복을 활용하여 효율적인 정렬 가능

❌ 단점

• 최악의 경우 O(n²)의 시간 복잡도를 가질 수 있음
• 재귀 호출이 많아 스택 오버플로우 발생 가능
• 안정적인 정렬이 아님 (Stable Sort가 아님)

6. 퀵 정렬이 적합한 경우

• 데이터의 개수가 많고 랜덤하게 분포된 경우
• 빠른 정렬 속도가 중요한 경우
• 메모리 사용을 최소화해야 하는 경우

 

 

퀵 정렬은 평균적으로 O(n log n)의 성능을 보장하는 빠른 정렬 알고리즘입니다. 하지만 최악의 경우 O(n²)로 성능이 저하될 수 있으므로, 피벗 선택 전략이 중요합니다.