퀵 정렬(Quicksort)

퀵 정렬은 분할 정복 전략을 사용한다

java에서 Arrays.sort는 DualPivotQuicksort를 사용한다.

최악의 경우 O(n^2)이고 평균적으로 O(n log n)이다

 

특정 값을 기준으로 그 값보다 작으면 앞으로 크면 뒤로 옮긴다

정렬이 될 때까지 반복한다

 

잘 구현하지 않으면 효율이 좋지 않다

 

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

public class QuickSort {
    //빅오 표기법 = 평균 O(nlogn) 최악 O(n^2)
    //퀵 정렬이 병합 정렬보다 빠른 이유는 상수 때문
    //백준 알고리즘 2751문제 - 퀵정렬로 안됨 병합정렬을 사용해야함 - 잘구현하면 됨
    //잘구현하지 않으면 효율이 안좋다
    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 n = Integer.parseInt(br.readLine());
        ArrayList<Integer> box = new ArrayList<>(n);
        for(int i = 0;i<n;i++){
            int x = Integer.parseInt(br.readLine());
            box.add(x);
        }
        ArrayList<Integer> output;
        output = quick(box);
        for(int i = 0;i<output.size();i++){
            bw.write(output.get(i)+"\n");
        }
        bw.flush();
        bw.close();

    }
    public static ArrayList<Integer> quick(ArrayList<Integer> arr){
        ArrayList<Integer> join = new ArrayList<>();
        if(arr.size()>0){
            int a = arr.get(0);
            ArrayList<Integer> low = new ArrayList<>();
            ArrayList<Integer> high = new ArrayList<>();
            for(int i = 1;i<arr.size();i++){
                if(arr.get(i)<a){
                    low.add(arr.get(i));
                }else{
                    high.add(arr.get(i));
                }
            }
            join.addAll(quick(low));
            join.add(a);
            join.addAll(quick(high));
        }
        return join;
    }
}