퀵 정렬(Quick Sort)

🔷 퀵 정렬(Quick Sort)란?

퀵 정렬은 "분할 정복(Divide and Conquer)" 전략을 기반으로 한 고성능 정렬 알고리즘입니다. 가장 널리 사용되는 정렬 알고리즘 중 하나로, 평균적으로 매우 빠른 속도를 보여줍니다.

 

퀵 정렬

✅ 작동 원리

퀵 정렬의 핵심은 **피벗(Pivot)**이라는 기준 값을 중심으로 배열을 두 부분으로 나누는 것입니다:

1. 피벗을 하나 선택합니다. (일반적으로 첫 요소, 마지막 요소, 혹은 중간값 등)
2. 배열을 피벗보다 작은 값과 큰 값으로 분할합니다.
3. 피벗을 기준으로 왼쪽과 오른쪽 서브 배열에 대해 퀵 정렬을 재귀적으로 반복합니다.
4. 모든 하위 배열이 정렬되면 전체 배열이 정렬됩니다.

✅ 시간 복잡도

• 평균: O(n log n)
• 최악 (피벗이 계속 가장 큰 값이나 가장 작은 값으로 선택될 경우): O(n²)
• 최선: O(n log n)
• 공간 복잡도: O(log n) (재귀 호출에 필요한 스택 메모리)

---

🔷 퀵 정렬의 장점과 단점

✅ 장점

• 평균적으로 매우 빠릅니다.
• 추가 메모리를 거의 사용하지 않습니다 (제자리 정렬).
• 대규모 데이터 정렬에 적합합니다.

❌ 단점

• 최악의 경우 성능이 O(n²)까지 떨어질 수 있습니다.
• 재귀 호출을 많이 사용하기 때문에 스택 오버플로우 위험이 있습니다.

---

🔷 Java 예제 코드

public class QuickSortExample {

    // 퀵 정렬 메서드
    public static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            // 파티션 기준점(피벗)을 구함
            int pivotIndex = partition(arr, low, high);

            // 피벗 기준 왼쪽, 오른쪽 각각 정렬
            quickSort(arr, low, pivotIndex - 1);
            quickSort(arr, pivotIndex + 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 printArray(int[] arr) {
        for (int num : arr) {
            System.out.print(num + " ");
        }
        System.out.println();
    }

    // 실행 메서드
    public static void main(String[] args) {
        int[] numbers = {7, 2, 1, 6, 8, 5, 3, 4};

        System.out.println("정렬 전 배열:");
        printArray(numbers);

        quickSort(numbers, 0, numbers.length - 1);

        System.out.println("정렬 후 배열:");
        printArray(numbers);
    }
}

 

✅ 출력 결과

정렬 전 배열:
7 2 1 6 8 5 3 4 
정렬 후 배열:
1 2 3 4 5 6 7 8

 

---

🔷 요약

항목설명

알고리즘 종류	분할 정복 기반 정렬
평균 성능	O(n log n)
공간 효율성	높음 (제자리 정렬)
주요 특징	빠르고, 재귀적 구조, 피벗 선택이 중요
적합한 경우	대용량 데이터, 성능이 중요한 환경