[알고리즘] 퀵정렬 Quick Function

퀵정렬

pivot을 이용해서 좌, 우측으로 정렬하는 기법

pivot은 맨 앞, 중간, 맨 뒤 등 임의로 설정할 수 있다.

평균 O(nlogn), 최악일 경우 O(n^2)의 시간 복잡도를 가진다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

class Main {
    public static int[] arr;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        arr = new int[N];

        for (int i=0; i<arr.length; i++) arr[i] = Integer.parseInt(br.readLine());
        quickSort(0, N-1);
        for (int a : arr) System.out.println(a);
    }

    public static void quickSort(int start, int end) {
        int pivot = arr[(start + end) / 2];
        int left = start, right = end;

        if (start >= end) return; // 종료 조건

        while (left <= right) {
            while (arr[left] < pivot) left++;
            while (arr[right] > pivot) right--;

            if (left <= right) {
                int tmp = arr[left];
                arr[left] = arr[right];
                arr[right] = tmp;
                left++;
                right--;
            }
        }

        if (start < right) quickSort(start, right);
        if (left < end) quickSort(left, end);
    }
}