[실전 문제] 퀵정렬 구현하기

1. 문제

N개의 자연수가 주어질 때, 퀵정렬을 이용하여 이를 정렬하는 프로그램을 작성하시오.

---

입력

첫 번째 줄에 N이 주어진다. ( 1 ≤ N ≤ 100,000 ) 두 번째 줄에 N개의 자연수가 주어진다. 

출력

퀵정렬을 이용하여 숫자를 오름차순으로 정렬한 결과를 출력한다.

예제 입력

case 1)

10
5 9 2 8 3 7 4 6 1 10

 

case 2)

5
2 3 1 2 1

예제 출력

case 1) 1 2 3 4 5 6 7 8 9 10

case 2) 1 1 2 2 3

 

 

 

2. 풀이

퀵 정렬은 기준(pivot)을 잡고 작은 수들은 왼쪽, 큰 수들은 오른쪽으로 나누어 정렬을 하는 고급 정렬이다. Arrays.sort를 이용하여 쉽게 정렬을 해도 좋으나, 퀵 정렬을 정확히 숙지하기 위해 직접 구현을 해봐야한다.

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

public class Main {

    private static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static final BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    private static int n;
    private static int[] arr;
    private static int[] left;
    private static int[] right;

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

        n = Integer.parseInt(br.readLine());

        arr = new int[n];
        left = new int[n];
        right = new int[n];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        quickSort(0, n-1);

        for(int i = 0; i < n; i++) {
            bw.write(arr[i] + " ");
        }

        br.close();
        bw.flush();
        bw.close();
    }

    private static void quickSort(int s, int e) {
        if(s >= e) return;

        // 가장 첫 번째 요소를 pivot으로 설정
        // pivot 보다 작은 요소를 left, pivot 보다 큰 요소를 right
        int pivot = arr[s];
        int leftCnt = getLeft(s+1, e, pivot);
        int rightCnt = getRight(s+1, e, pivot);

        for(int i = 0; i < leftCnt; i++) {
            arr[s+i] = left[i];
        }

        arr[s+leftCnt] = pivot;

        for(int i = 0; i < rightCnt; i++) {
            arr[s+leftCnt+1+i] = right[i];
        }
        quickSort(s, s+leftCnt-1);
        quickSort(s+leftCnt+1, e);
    }

    private static int getLeft(int s, int e, int pivot) {
        int idx = 0;
        for(int i = s; i <= e; i++) {
            if(arr[i] <= pivot) left[idx++] = arr[i];
        }
        return idx;
    }

    private static int getRight(int s, int e, int pivot) {
        int idx = 0;
        for(int i = s; i <= e; i++) {
            if(arr[i] > pivot) right[idx++] = arr[i];
        }
        return idx;
    }
}