• 기본 퀵 정렬 코드

이론

퀵 정렬은 기준값(pivot)을 선정해 해당 값보다 작은 데이터와 큰 데이터로 분류하는 것을 반복해 정렬하는 알고리즘이다. 기준값이 어떻게 선정되는지가 시간 복잡도에 많은 영향을 미치고, 평균 시간 복잡도는 O(nlogn)이며 최악의 경우에는 시간 복잡도가 O(n²)이 된다.

퀵 정렬 수행 방식

<aside> 💡 pivot을 중심으로 계속 데이터를 2개의 집합으로 나누면서 정렬하는 것이 퀵 정렬의 핵심이다.

</aside>

퀵 정렬의 시간 복잡돈느 비교적 준수하므로 코딩 테스트에서도 종종 응용한다. 재귀 함수의 형태로 직접 구현해 볼 것을 추천한다.

K번째 수 구하기

문제 설명

문제 분석

슈도코드

구현

public class K번째수구하기_11004 {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int N = scan.nextInt();
        int K = scan.nextInt();
        int[] arr = new int[N];
        for(int i=0; i<N; i++){
            arr[i] = scan.nextInt();
        }

        quickSort(arr, 0, N-1, K-1);
        System.out.println(arr[K-1]);
    }

    public static void quickSort(int[] arr, int start, int end, int K){
        if(start < end) {
            int pivot = findPivot(arr, start, end);

            if(pivot == K) { // K번째 수가 pivot이면 더이상 구할 필요 없음
                return;
            } else if(K < pivot) { // K가 pivot보다 작으면 왼쪽 그룹만 정렬 수행
                quickSort(arr, start, pivot-1, K);
            } else { // K가 pivot보다 크면 오른쪽 그룹만 정렬 수행
                quickSort(arr, pivot + 1, end, K);
            }
        }
    }

    public static int findPivot(int[] arr, int start, int end) {

        // 데이터가 2개인 경우
        if((start + 1) == end) {
            if(arr[start] > arr[end]) {
                swap(arr, start, end);
            }
            return end;
        }

        int mid = (start + end) / 2;
        swap(arr, start, mid); // 중앙을 1번째 요소로 사용
        int pivot = arr[start];
        int i = start + 1;
        int j = end;

        while(i <= j) {
            while(pivot < arr[j] && j > 0){ // pivot보다 작은 수가 나올 때 까지 j--
                j--;
            }
            while(pivot > arr[i] && i < arr.length-1) { // pivot보다 큰 수가 나올 때 까지 i++
                i++;
            }
            if(i <= j){
                swap(arr, i++, j--);
            }
        }

        // i==j pivot의 값을 양쪽으로 분리한 후의 가운데에 위치하도록
        arr[start] = arr[j];
        arr[j] = pivot;
        return j;
    }

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