019 : Quick sort / K번째 수 구하기

Klocated 자체는 말 그대로 void로서 TP[] 를 정렬하는 것이지, 특별히 k를 Return하지 않는다(OEC에서 정렬된 TP[k-1]에 액세스)

 

TP[] connector, 시작과 끝 pointer, target k가 필요

 

그리고 해당 인자들로 quickSort 공급도 필요하다

 

if는 recursive bottom

또 Klocated는 하청을 주는  것 / 탐색 구간만 받아서 quickSort으로 넘겨줌

 

 

 

 

 

 

EP 최소 피스 작업

 

 

 

 

 

 

 

 

 

pivot을 s pointer와 바꾸어 setup

작업의 기본이 되는 비교를 위해 해당 value는 먼저 보관하고 swap한다

 

마지막에 다시 되돌려 놓을 것

 

quickSort는 정렬 후 pivot pointer를 전달

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

통상적인 Quick sort는

한번 정렬된 pivot의 양쪽을 모두 탐색해야 하지만

Target < Pivot 일 때 

0 ~ (pivot-1) 까지만 탐색하면 됨

 

 

 

 

 

 

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

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

        // IRC - L1
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int C = Integer.parseInt(st.nextToken());
        int T = Integer.parseInt(st.nextToken());

        // L2
        st = new StringTokenizer(br.readLine());
        int[] F = new int[C];
        for (int i = 0; i < C; i++) {
            F[i] = Integer.parseInt(st.nextToken());
        }

        // Factory
        quickSort(F, 0, C-1, T-1);

        // OSC
        System.out.println(F[T-1]);
    }

    // External Module(1/3) : quicksort
    public static void quickSort (int[] F, int S, int E, int T) {

        if (S < E) {

            // 피벗 선정은 물론, quick sort까지 완료됨
           int pivot = partition(F, S, E);

            if (pivot == T)
                return;
            else if (T < pivot)
                quickSort(F, S, pivot - 1, T);
            else
                quickSort(F, pivot + 1, E, T);
        }
    }

    // External Module(2/3) : partition
    public static int partition(int[] F, int S, int E) {

        // 특이케이스 먼저 해소 : 공간이 계속 수축되어 마지막 2개가 남았을 떄
        if (S+1 == E) {
            if (F[S] > F[E])
                swap(F, S, E);
            return E;
        }

        // 중간값으로 피벗 설정하고, 첫번째랑 swap
        int M = (S + E) / 2;
        swap(F, S, M);
        int pivot = F[S];

        // 첫번쨰 = 피봇, 두번쨰 ~ 끝에서 quicksort 시작
        int i = S + 1, j = E;
        while (i <= j) {

            // 피벗보다 크다면 (이미 정렬 완료된거니) 그대로 두고 좁혀오면서 다음것 탐색
            while (pivot < F[j] && j > 0) {
                j--;
            }

            // 피벗보다 작다면 (이미 정렬 완료된거니 )그대로 두고 좁혀나가면서 다음것 탐색
            while (pivot > F[i] && i < F.length - 1) {
                i++;
            }

            // 그럼에도 여전히 i < j라면, 중간에 while 조건을 충족해 후크 락이 걸리는 경우임
            // 만나거나, 떨어져 있음
            if (i <= j) {
                swap (F, i++, j--); // i j 스왑이 아닌, 왜 i++ j-- 한번더 가는지 > 가능성공간 : while이 어디서 끊어지는지 탐색할것
            }
        }
        F[S] = F[j];
        F[j] = pivot;
        return j;
    }

    // External Module (3/3) : Swap
    public static void swap(int[] F, int i, int j) {
        int temp = F[i];
        F[i] = F[j];
        F[j] = temp;
    }
}