퀵 선택 정렬(Quick Selection Sort)에 대해 알아보자

이번 포스팅은 퀵 정렬의 변형 방법인 퀵 선택 정렬에 대해서 알아보도록 하겠다. 퀵 선택 정렬은 정렬한 수에서 K번째 숫자를 구할 때 유용하게 사용되는 정렬 알고리즘이다. 일반 정렬 방법으로 K번째 수를 찾으려면 모든 숫자를 정렬한 뒤에야 찾고자 하는 숫자를 찾을 수 있지만 퀵 선택 정렬을 이용하면 모든 숫자를 검색하지 않고 숫자를 찾을 수 있다.

퀵 정렬에서는 피벗을 설정하고 피벗 앞과 뒤를 나누어 정렬한다. 피벗의 앞쪽은 무조건 피벗보다 작고 뒤쪽은 피벗보다 크다. 만약 찾고자 하는 숫자 K의 인덱스가 피벗의 인덱스보다 크다면 피벗의 앞쪽을 정렬할 필요가 있을까? 이 생각을 이용한 것이 퀵 선택 정렬이다. 매번 피벗의 인덱스와 K의 인덱스를 비교해 K의 인덱스가 피벗의 인덱스보다 작다면 피벗의 앞쪽만 다시 정렬하고 피벗보다 크다면 뒤쪽만 정렬을 한다. 이것을 반복하다보면 실제 K번째 수가 피벗이 되는 일이 발생하는데 이때가 정답이다. 백준 11004번이 이 문제이다.

https://www.acmicpc.net/problem/11004

11004번: K번째 수

퀵 선택 정렬을 사용하면 되지만 피벗을 선택하는 방법에 따라 시간 초과가 나올 수 있다. 아마 맨 앞이나 맨 뒤를 피벗으로 선택하는 경우에 대한 최악의 경우를 테스트케이스에 넣어놓지 않았나 추정된다. 따라서 중간 숫자를 사용하던지 무작위 3개를 뽑아 중간값을 사용해 보자. 구현은 더 어렵겠지만 좋은 공부가 될 것이다.

다음 코드는 내가 작성한 코드이다.

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
        st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine());
        int[] array = new int[N];
        for(int i=0;i<N;i++){
            array[i] = Integer.parseInt(st.nextToken());
        }
        quickSort(array, 0, N-1, k-1);
        bw.write(array[k-1]+"");
        bw.flush();
        bw.close();
    }
    static void quickSort(int[] array, int start, int end, int k){
        if(end-start < 1) return;
        else if(end-start==1){
            if(array[start]>array[end]){
                swap(array, start, end);
            }
            return;
        }
        int pivotIndex = (start+end)/2;
        int pivot = array[pivotIndex];
        swap(array, start, pivotIndex);
        int i = start + 1;
        int j = end;
        while(i <= j){
            while(array[i] < pivot && i<=end){
                i++;
            }
            while(array[j] > pivot && j>start){
                j--;
            }
            if(i <= j){
                swap(array, i++, j--);
            }
        }
        swap(array, start, j);
        if(k==j){
            return;
        }else if(k>j){
            quickSort(array, j+1, end, k);
        }else{
            quickSort(array, start, j-1, k);
        }
    }
    static void swap(int[] array, int a, int b){
        int c = array[b];
        array[b] = array[a];
        array[a] = c;
    }
}

나는 투 포인터를 이동시킬 때 조건문에 등호가 들어가느냐 마냐가 제일 헷갈렸던 것 같다. 그리고 swap을 하면서 i와 j를 ++과 --로 연산해 줘야 동일한 숫자가 있을 때 루프에서 빠져나올 수 있다. 이러지 않으면 무한 반복문을 돌게 된다. 나도 알고 싶지 않았다. 여기서는 피벗을 배열 인덱스의 중간값으로 설정하였다. 양 끝단은 시간 초과가 난다. 처음에 가장 떠올리기 힘들었던 아이디어는 swap에 ++을 넣는 것이었다. 항상 따로 연산해야 한다는 생각이 있어서 그랬던 것 같다. 앞으로는 이것도 고려하면서 코딩해야겠다.