[JAVA] 백준 2750 : 수 정렬하기

이전에 공부한 퀵정렬을 이용했다

import java.io.*;

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));
        
        int count = Integer.parseInt(br.readLine());
        int[] arr = new int[count];
        for(int i = 0; i < count; i++){
            arr[i] = Integer.parseInt(br.readLine());
        }
        sort(arr);

        for(int i = 0; i < count; i++){
            bw.write(String.valueOf(arr[i]));
            bw.newLine();
        }

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

    public static void sort(int[] arr) {
        quickSort(arr, 0, arr.length - 1);
    }

    public static void quickSort(int[] arr, int start, int end) {
        // 파티션을 나누고 오른쪽 파티션의 첫번째 자리
        // 즉 한번 정렬하고 start와 end가 교차된 후 start의 자리
        int part2start = partition(arr, start, end);
        //오른쪽 파티션의 시작점과 왼쪽파티션 크기를 비교하여 왼쪽파티션 크기가 2이상일때 다시 정렬
        if (start < part2start - 1) quickSort(arr, start, part2start - 1);
        // 오른쪽 파티션의 시작점과 배열의 끝의 크기가 1을 초과할 때 오른쪽도 정렬
        if (end > part2start) quickSort(arr, part2start, end);
    }
    // 파티션 나누는 메서드
    public static int partition(int[] arr, int start, int end) {
        // 피벗은 배열의 중간으로 임의지정
        int pivot = arr[(start + end) / 2];

        // start와 end가 교차하기 전에는 계속 반복
        while (start <= end) {
            // arr의 start값이 pivot보다 큰값이 발견될 때까지 반복
            while (arr[start] < pivot) start++;
            // arr의 end 값이 pivot보다 작은 값이 발견될 때까지 반복
            while (arr[end] > pivot) end--;
            // 반복을 끝내고 start와 end가 교차했는지 확인
            if (start <= end) {
                //교차하지 않았으면 서로 자리를 바꾸고 start와 end를 한칸씩 전진
                swap(arr, start, end);
                start++;
                end--;
            }
        }
        // 교차를 했다면 start가 오른쪽 파티션의 시작점이 되니 start를 반환
        return start;
    }
    // 자리바꾸는 메서드
    public static void swap(int[] i, int start, int end) {
        int temp = i[start];
        i[start] = i[end];
        i[end] = temp;
    }
}