퀵선택 알고리즘

퀵선택 알고리즘은 특정 위치의 원소를 찾는 데 사용되는 효율적인 분할 정복 알고리즘 중 하나이다.

퀵정렬 알고리즘 일부를 이용하여 전체를 정렬하지 않고 특정 위치의 원소를 찾을 수 있다.

이 알고리즘의 평균 시간 복잡도는 O(n)이며, 최악의 경우에 O(n^2)이 될 수 있다.

 

동작 순서

1. 피벗 선택: 배열에서 피벗을 선택한다. 일반적으로 배열의 가운데 원소를 선택한다.
2. 분할: 피벗을 기준으로 배열을 두 그룹으로 나눈다. 작은 원소는 피벗 왼쪽에 위치하고, 큰 원소는 오른쪽에 위치한다.
3. 쿼리 위치 확인: 찾고자 하는 원소의 위치를 확인한다. 이 위치가 현재 피벗의 위치와 일치하면 찾은 것이다.
4. 재귀적으로 반복: 찾고자 하는 위치가 피벗의 위치보다 작으면 왼쪽 부분 배열에서 반복적으로 알고리즘을 수행한다. 반대로 크면 오른쪽 부분 배열에서 반복한다.

 

public class QuickSelect {
	
    /**
     * 배열에서 주어진 순서에 해당하는 요소를 선택하는 메서드
     * @param arr 배열
     * @param order 순서 (1부터 시작)
     * @return 선택된 요소
     */
    public static int quickSelect(int[] arr, int order) {
        return quickSelect(arr, 0, arr.length - 1, order - 1);
    }

    /**
     * 배열에서 주어진 범위 내에서 주어진 순서에 해당하는 요소를 선택하는 재귀 메서드
     * @param arr 배열
     * @param start 범위의 시작 인덱스
     * @param end 범위의 끝 인덱스
     * @param order 순서
     * @return 선택된 요소
     */
    private static int quickSelect(int[] arr, int start, int end, int order) {
        if (start > end) {
            return -1;
        }
        int pivotIndex = partition(arr, start, end);

        if (pivotIndex == order) {
            return arr[pivotIndex];
        } else if (pivotIndex < order) {
            return quickSelect(arr, pivotIndex + 1, end, order);
        } else {
            return quickSelect(arr, start, pivotIndex - 1, order);
        }
    }

    /**
     * 배열의 특정 범위를 피벗을 기준으로 분할하는 메서드
     * @param arr 배열
     * @param start 범위의 시작 인덱스
     * @param end 범위의 끝 인덱스
     * @return 피벗의 인덱스
     */
    private static int partition(int[] arr, int start, int end) {
        int middle = (start + end) / 2;
        int pivot = arr[middle];
        // pivot을 start 위치로 옮기기
        swap(arr, start, middle);

        int leftPointer = start + 1;
        int rightPointer = end;

        while (leftPointer <= rightPointer) {
            while (leftPointer <= rightPointer && arr[leftPointer] < pivot) {
                leftPointer++;
            }

            while (leftPointer <= rightPointer && arr[rightPointer] > pivot) {
                rightPointer--;
            }

            if (leftPointer <= rightPointer) {
                swap(arr, leftPointer, rightPointer);
                leftPointer++;
                rightPointer--;
            }
        }
        // rightPointer 오른쪽으로는 pivot보다 큰 수들만 존재한다.
        swap(arr, start, rightPointer);
        // rightPointer의 위치에 pivot이 들어간다.
        return rightPointer;
    }

    /**
     * 배열의 두 요소를 교환하는 메서드
     * @param arr 배열
     * @param i 교환할 요소의 인덱스
     * @param j 교환할 요소의 인덱스
     */
    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[