알고리즘 개념[기초] - 퀵 정렬

퀵정렬은 기준값을 선정하여 큰 데이터와 작은 데이터를 분류하는 것을 반복하여 정렬하는 알고리즘입니다.

기준값을 선정하는 것이 핵심이며, 이에 따라 시간 복잡도에 많은 영향을 미칩니다.

평균적인 시간 복잡도 : O(nlogn) - 병합정렬

핵심 이론은 기준값을 중심으로 데이터를 2개의 집합으로 나누면서 정렬하는 것이 퀵 정렬의 핵심입니다.

퀵 정렬 과정 은 다음과 같습니다.

1. 피벗을 하나 선택합니다.
2. 피벗을 준으로 양쪽에서 피벗보다 크거나 작은 값을 찾습니다. 왼쪽에서부터는 피벗보다 큰 값을 찾고, 오른쪽에서부터는 피벗보다 작은 값을 찾습니다.
3. 양 방향에서 찾은 두 원소를 교환합니다.
4. 왼쪽에서 탐색하는 위치와 오른쪽에서 탐색하는 위치가 엇갈리지 않을 때까지 2번으로 돌아가 위 과정을 반복합니다.
5. 엇갈린 기점을 기준으로 두 개의 부분리스트로 나누어 1번으로 돌아가 해당 부분리스트의 길이가 1이 아닐 때까지 1번 과정을 반복합니다.
6. 인접한 부분리스트끼리 합쳐줍니다.

즉, 퀵정렬의 큰 특징은 '피벗'을 하나 설정하고 피벗보다 작은 값들은 왼쪽에, 큰 값들은 오른쪽에 치중하도록 하는 것이며, 이 과정을 파티셔닝(Partitioning) 이라고 한다.

구현

public class 퀵정렬 {
    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 < N; i++){
            arr[i] = (int)(Math.random()*N);//0~9
        }

        System.out.println("정렬 전 : " + Arrays.toString(arr));
        
        quick_sort(arr, 0, N-1);

        System.out.println("정렬 후 : " + Arrays.toString(arr));
    }

    static void quick_sort(int[] arr, int low, int high){
        if(low >= high)
            return;

        int pivot = partition(arr,low, high);

        quick_sort(arr, low, pivot);
        quick_sort(arr, pivot+1, high);
    }

    static int partition(int[] arr, int left, int right){

        int low = left-1; // -1
        int high = right+1; // N
        int pivot = arr[(left+right)/2]; // 중간 pivot

        while(true){
            while(arr[++low] < pivot);
            while(arr[--high] > pivot && high >= low);

            if(low >= high)
                return high;
            
            swap(arr,low,high);
        }
    }

    static void swap(int[] arr, int i, int j){
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
}