초보 자바 프로그래밍(22) - 퀵정렬 (Quick Sort)

퀵 정렬 대표 이미지

🔖 INDEX

 

 

퀵 정렬(Quick Sort)은 분할 정복(Divide and Conquer) 전략을 사용하는 비교 기반 정렬 알고리즘입니다. 퀵 정렬은 배열을 피벗(pivot)이라 불리는 기준 원소를 선택한 후, 피벗보다 작은 원소와 큰 원소로 분할합니다. 그 후, 분할된 두 하위 배열에 대해 동일한 방식으로 퀵 정렬을 재귀적으로 적용하여 전체 배열을 정렬합니다.

 

퀵 정렬의 작동 원리

퀵 정렬의 작동 원리는 다음과 같습니다:

1. 배열에서 피벗을 선택합니다. 피벗 선택 방법에 따라 성능에 큰 영향을 줄 수 있으며, 일반적으로 처음, 가운데, 마지막 원소 중 하나를 선택하거나, 무작위로 선택하기도 합니다.
2. 피벗을 기준으로 배열을 분할합니다. 피벗보다 작은 원소들은 왼쪽 하위 배열에, 큰 원소들은 오른쪽 하위 배열에 배치합니다. 이 과정을 분할(Partition)이라고 합니다.
3. 왼쪽과 오른쪽 하위 배열에 대해 재귀적으로 퀵 정렬을 수행합니다. 하위 배열의 크기가 1 이하가 되면 정렬이 완료된 것으로 간주하고 재귀를 종료합니다.
4. 모든 하위 배열이 정렬되면 전체 배열이 정렬됩니다.

 

퀵 정렬의 특징

퀵 정렬의 특징은 다음과 같습니다:

1. 불안정한 정렬(Unstable Sort): 같은 값의 원소들이 정렬 과정에서 상대적인 순서가 변경될 수 있습니다.
2. 제자리 정렬(In-place Sort): 입력 배열 안에서 정렬이 이루어지며, 추가적인 메모리를 사용하지 않습니다.
3. 시간 복잡도(Time Complexity): 최선 및 평균적인 경우 시간 복잡도는 O(n log n)입니다. 그러나 최악의 경우 시간 복잡도는 O(n^2)로, 이는 피벗 선택 전략에 크게 의존합니다.

 

 

퀵 정렬의 장점

• 평균적으로 빠른 성능: 평균적인 경우 O(n log n)의 시간 복잡도를 가지며, 일반적으로 병합 정렬보다 상수 시간이 적게 소요됩니다.
• 메모리 사용량이 적음: 제자리 정렬 알고리즘으로서 추가적인 메모리를 사용하지 않습니다.
• 적용이 간편: 코드 구현이 상대적으로 간단하며, 다양한 데이터 타입과 구조에 적용하기 쉽습니다.

 

퀵 정렬의 단점

• 불안정한 정렬: 같은 값의 원소들이 정렬 과정에서 상대적인 순서가 변경될 수 있습니다. 이로 인해 안정성이 요구되는 경우에는 다른 알고리즘을 사용하는 것이 좋습니다.
• 최악의 경우 성능 저하: 피벗 선택 전략에 따라 최악의 경우 시간 복잡도가 O(n^2)로 증가할 수 있습니다. 이는 이미 정렬된 배열이나 거의 정렬된 배열에서 발생할 수 있습니다. 이 문제를 완화하기 위해 무작위 피벗 선택이나 중앙값을 피벗으로 선택하는 방법이 사용됩니다.

 

퀵 정렬의 구현 예제

퀵 정렬은 자바에서 다음과 같이 구현할 수 있습니다.

 

 

// QuickSort 클래스 선언
public class QuickSort {
    // 퀵 정렬 알고리즘을 수행하는 함수
    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);
        }
    }

    // 배열을 피벗을 기준으로 분할하고 피벗 인덱스를 반환하는 함수
    private 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++;
                swap(arr, i, j);
            }
        }
        // 피벗을 배열의 중앙에 배치하고 인덱스를 반환
        swap(arr, i + 1, high);
        return i + 1;
    }

    // 두 배열 원소를 서로 교환하는 함수
    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

퀵 정렬은 피벗 선택 전략에 크게 의존하므로, 피벗 선택 전략을 신중하게 결정해야 합니다. 좋은 피벗 선택 전략은 배열의 일부만을 사용하여 피벗을 선택하거나, 무작위로 피벗을 선택하는 것입니다. 이러한 전략을 사용하면 최악의 경우 시간 복잡도를 줄일 수 있습니다.

 

또한, 재귀 호출의 깊이가 배열의 크기에 비례할 수 있으므로, 스택 오버플로의 위험이 있습니다. 이를 방지하기 위해 반복적인 구현이나, Tail-call 최적화를 적용할 수 있습니다.

 

퀵 정렬은 일반적으로 평균적인 성능이 좋기 때문에 다양한 상황에서 사용할 수 있는 알고리즘입니다. 그러나 안정성이 중요한 상황에서는 병합 정렬이나 팀 정렬 등 안정적인 정렬 알고리즘을 사용하는 것이 좋습니다.