# 퀵 정렬

### K번째 수 구하기

#### Question - 11004

![](https://2669959621-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FxncaDDrGpdjhVy86HbwM%2Fuploads%2FhL04NLC63cjqjHwph2mG%2F%E1%84%89%E1%85%B3%E1%84%8F%E1%85%B3%E1%84%85%E1%85%B5%E1%86%AB%E1%84%89%E1%85%A3%E1%86%BA%202022-06-08%20%E1%84%8B%E1%85%A9%E1%84%8C%E1%85%A5%E1%86%AB%2011.59.35.png?alt=media\&token=0725e78b-1708-4a94-8016-4cc528dd35eb)

#### Code

{% tabs %}
{% tab title="함수" %}
```java
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class N19_P11004_K번째_수_구하기 {

    public static void main(String[] args) throws IOException {

        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(in.readLine());

        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(in.readLine());
        int[] A = new int[N];
        for (int i = 0; i < N; i++) {
            A[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(A);

        System.out.println(A[K-1]);
    }
}

```
{% endtab %}

{% tab title="퀵 정렬" %}
* 시간 초과 됨

```java
import java.io.BufferedReader;
import java.util.StringTokenizer;
import java.io.IOException;
import java.io.InputStreamReader;


public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(in.readLine());
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(in.readLine());
        int[] A = new int[N];
    
        for(int i = 0; i < N; i++) {
            A[i] = Integer.parseInt(st.nextToken());
        }
    
        quickSort(A, 0, N - 1, K - 1);
        System.out.println(A[K - 1]);
    
    }

    public static void quickSort(int[] A, int S, int E, int K) {
    
        if(S < E) {
            int pivot = partition(A, S, E);
            if(pivot == K)
                return ;
            else if (K < pivot)
                quickSort(A, S, pivot - 1, K);
            else 
                quickSort(A, pivot + 1, E, K);
        
        }
    }

    public static int partition(int[] A, int S, int E) {
    
        int M = (S + E) / 2;
        swap(A, S, M);
        int pivot = A[S];
        int i = S, j = E;
    
        while (i < j) {
            while (pivot < A[j]) {
                j--;
            }
            while (i < j && pivot >= A[i]) {
                i++;
            }
            swap(A, i, j);
        }
    
        A[S] = A[i];
        A[i] = pivot;
        return i;

    }

    public static void swap(int[] A, int i, int j) {
        int temp = A[i];
        A[i] = A[j];
        A[j] = temp;
    }
}
```


{% endtab %}
{% endtabs %}

#### Idea

* 정렬

#### reference
