분할 정복 이용해 k번째 작은 수 구하기

퀵 소트와 비슷한 방법으로 분할 정복을 이용해 구할 수 있다.

public class Main
{
    public static int partition(int[] arr, int start, int end)
    {
        int i = start + 1; // p보다 작거나 같은 요소들 시작 부분
        int j = end; // p보다 큰 요소들 시작 부분
        int temp;
        while (i <= j)
        { // 제자리일떄 한칸씩 다음으로
            if (arr[i] <= arr[start]) i++; // 작거나 같은 요소들 제자리에 있을때
            else if (arr[j] > arr[start]) j--; // 큰 요소들 제자리에 있을때
            else // 둘다 제자리 아닐때 스왑 후 각각 한칸씩
            {
                temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
                i++;
                j--;
            }
        } // i > j시 종료 후 p와 작거나 같은값 끝 요소 스왑
        temp = arr[start];
        arr[start] = arr[j];
        arr[j] = temp;
        
        return j; // 자리 확정된 pivot값 반환
    }
    
    public static int sel(int[] arr, int start, int end, int k)
    { // 배열 내에서 k번째 작은 요소 구함
        int p, s;
        p = partition(arr, start, end);
        s = p-start; // arr[p]보다 작은 요소들의 수(small 그룹)
        if (k <= s)
        { // k가 small그룹 요소수 보다 작다면 small 그룹에서 찾기
            return sel(arr, start, p-1, k);
        }
        else if (k == s+1)
        { // k가 small그룹 바로 다음 요소일때(k 찾았을때)
            return arr[p];
        }
        else
        { // large그룹에서 찾기
            return sel(arr, p+1, end, k-s-1);
        }
    }
    
    public static void printArr(int[] arr)
    {
        for (int i=0; i<arr.length; i++)
		    System.out.print(arr[i]+" ");
		 System.out.println();
    }
    public static void main(String[] args)
    {
        int[] arr = {91, 85, 68, 70, 98, 24, 1,2,3,4,6,7,8,9};
        int k = 5;
        System.out.println(sel(arr, 0, arr.length-1, k));
    }
}

시간 복잡도는 최선의 경우(찾는 값이 기준 요소일때) θ(N)이지만, 최악의 경우(퀵 소트와 마찬가지로 정렬되어 있어서 한 그룹은 비어있고, 다른 그룹은 기준 요소 제외한 모든 요소 담겨있을때) θ(N^2)이다.
하지만 평균 시간복잡도는 θ(N)이다.