K번째 수 (quick sort)

N개의 수가 주어진다. 이 수들을 오름차순 정렬했을 때, K번째에 위치하는 수를 알아내자.

입력

첫 번째 줄에 N, K가 공백으로 분리되어 주어진다. (1 ≤ K ≤ N ≤ 5,000,000)

두 번째 줄부터 N개의 줄에 걸쳐 N개의 정수가 주어진다. 각 정수는 -1,000,000,000 이상 1,000,000,000 이하이다.

출력

주어진 N개의 정수를 오름차순 정렬했을 때, K번째에 위치하는 수를 출력한다.

문제는 심플하다..

단순 sort후 K 번째 숫자를 출력하고 싶지만.

정수의 범위가 커서 일반 sort할 경우, time out 이 발생한다.

지금의 예제는 중간값을 구하고,

그 값을 기준으로 quick sort를 반복한다.

좀더 빠르게 하려면, 중간값을  처음과 끝의 반복이 아닌

첫 수, 마지막 수, 중간수를  뽑아서 중간값을 할경우 nlogn의 횟수를 피할수 있다고 한다..

아직 안해봄..

import java.io.BufferedReader; import java.io.FileInputStream; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer;   public class source {           static int[] su;     static int N, K;     public static void main(String[] args) throws IOException {         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));                   StringTokenizer token = new StringTokenizer(br.readLine(), " ");                   N = Integer.parseInt(token.nextToken());         K = Integer.parseInt(token.nextToken());         su = new int[N+5];                   for (int i = 1; i < N+1; i++) {             su[i] = Integer.parseInt(br.readLine());         }                       System.out.println(sort(1,N));     }           public static int sort(int l, int r){                   if(l == r) return su[l];           int left = l - 1;         int right = r + 1;         int pivot = su[(l+r) >> 1];         int temp;                   do{             while(su[++left] < pivot);             while(su[--right] > pivot);             if(left >= right) break;                 temp = su[left];                 su[left] = su[right];                 su[right] = temp;         }while (left < right);           if(left==right && left==K) return pivot;         if(K < left) return sort(l, left-1);         return sort(right+1, r);     }   }