<Algorithm> 59. 11004번 K번째 수(Quick & Merge Sort)

1. 11004번 K번째 수

• 기본 정렬 문제, Arrays.sort를 사용하면 간단하지만 Quick, Merge 정렬을 직접 만들어서 해결하는 것이 좋을 것 같다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class Main {
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br =new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine());
        int[] arr = new int[N];
        
        for(int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        //Arrays.sort(arr);
        //quickSort(arr, 0, arr.length - 1);
        int[] temp = new int[arr.length];
        merge(arr, temp, 0, arr.length - 1);
        System.out.println(arr[K-1]);
    }
    
    public static void quickSort(int[] arr, int start, int end) {
        int res = partition(arr, start, end);
        if(start < res - 1) {
            // 0보다 클때 실행 (오른쪽에 하나라도 있을때)
            quickSort(arr, start, res - 1);
        } // 왼쪽탐색
        if(end > res) {
            quickSort(arr, res, end);
        }// 오른쪽 탐색
        
    }
    public static int partition(int[] arr, int start, int end) {
        int pivot = arr[(start+end)/2];
        while(start<=end) {
            while (arr[start] < pivot) start++;
            while (arr[end] > pivot) end--;
            if(start<=end) {
                int temp = arr[start];
                arr[start] = arr[end];
                arr[end] = temp;
                start++;
                end --;
            }
        }
        return start;
    }
    
    
    public static void merge(int[] arr,int[] temp, int start, int end) {
        if(start < end) {
            int middle = (start + end) / 2;
            merge(arr, temp, start, middle);
            merge(arr, temp, middle + 1, end);
            // 제일 작게 분할 
            merge(arr, temp, start, end, middle);
            
        }
    }
    
    public static void merge(int[] arr,int[] temp, int start, int end ,int middle) {
        for(int i = start; i <= end; i++) {
            temp[i] = arr[i];
        }
        int part1 = start;
        int part2 = middle + 1;
        int index = start;
        while(part1 <= middle && part2 <= end) {
            // 대소비교
            if(temp[part1] <= temp[part2]) {
                // 앞에있는것이 더 작을 경우
                arr[index] = temp[part1];
                //원본 배열에 저장
                part1++;
            }else {
                arr[index] = temp[part2];
                part2++;
            }
            index ++ ;
        }
        for(int i = 0; i <= middle - part1; i++) {
            arr[index + i] = temp[part1 + i];
        } //앞쪽배열이 남아 있는 경우 
        
    }
}
 

출처

https://youtu.be/QAyl79dCO_k  병합정렬

https://youtu.be/7BDzle2n47c 퀵정렬