정렬(2) 퀵 정렬(Quick Sort)

1. 퀵 정렬 개념

• 퀵 정렬은 분할 정복(Divide and Conquer) 방식을 사용하여 정렬합니다.

• 평균적으로 매우 빠른 성능을 보여주며, 평균 시간 복잡도는 𝑂(nlogn)입니다.

2. 퀵 정렬의 동작 방식

• 기준 값 선택 (Pivot Selection): 배열에서 하나의 요소를 선택하여 기준 값(pivot)으로 설정합니다. 기준 값은 배열의 중앙, 처음, 끝 또는 랜덤하게 선택할 수 있습니다.

• 분할 (Partitioning): 기준 값을 기준으로 배열을 두 부분으로 나눕니다. 기준 값보다 작은 값들은 기준 값의 왼쪽으로, 큰 값들은 오른쪽으로 이동합니다. 이 과정을 통해 기준 값은 최종 정렬 위치에 놓이게 됩니다.

• 재귀적 정렬 (Recursive Sorting): 분할된 두 부분에 대해 재귀적으로 퀵 정렬을 수행합니다. 이 과정을 배열의 크기가 1 이하가 될 때까지 반복합니다.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class QuickSort {

    public static List<Integer> quicksort(List<Integer> arr) {
        if (arr.size() <= 1) {
            return arr;
        }
        
        int pivot = arr.get(arr.size() / 2);
        List<Integer> left = new ArrayList<>();
        List<Integer> middle = new ArrayList<>();
        List<Integer> right = new ArrayList<>();
        
        for (int x : arr) {
            if (x < pivot) {
                left.add(x);
            } else if (x == pivot) {
                middle.add(x);
            } else {
                right.add(x);
            }
        }
        
        List<Integer> sortedLeft = quicksort(left);
        List<Integer> sortedRight = quicksort(right);
        
        List<Integer> sortedArr = new ArrayList<>();
        sortedArr.addAll(sortedLeft);
        sortedArr.addAll(middle);
        sortedArr.addAll(sortedRight);
        
        return sortedArr;
    }

    public static void main(String[] args) {
        List<Integer> arr = Arrays.asList(3, 6, 8, 10, 1, 2, 1);
        List<Integer> sortedArr = quicksort(arr);
        System.out.println(sortedArr);
    }
}

3. 퀵 정렬의 장점

• 빠른 성능: 퀵 정렬은 평균적으로 𝑂(nlogn)의 시간 복잡도를 가지며, 실제로 많은 경우에 매우 빠르게 동작합니다.

• 메모리 효율성: 퀵 정렬은 제자리(in-place) 정렬로, 추가적인 메모리 사용이 최소화됩니다.

4. 퀵 정렬의 단점

• 최악의 경우 성능: 피벗 선택이 항상 최악으로 이루어지면, 시간 복잡도가
  𝑂(n^2)로 떨어질 수 있습니다.

• 불안정성: 퀵 정렬은 안정적이지 않아 동일한 값의 순서가 보장되지 않습니다.