[Algorithm] 퀵 정렬 (Quick Sort)

오름차순

import java.util.Scanner;

public class quickSort {
    public static void swap(int[] arr, int p1, int p2){
        int tmp = arr[p1];
        arr[p1] = arr[p2];
        arr[p2] = tmp;
    }

    // 분할
    public static int partition(int[] arr, int start, int end){
        int key = start;
        int lt = start + 1;
        int rt = end;

        while(lt <= rt){ // 엇갈릴 때까지 반복
            while( lt <= end && arr[lt] <= arr[key] ){ // 키 값보다 큰 값을 만날 때 까지
                lt++;
            }

            while(arr[rt] >= arr[key] && rt > start){ // 키 값보다 작은 값을 만날 때 까지
                rt--;
            }

            if(lt > rt) { // 현재 엇갈린 상태이면 키 값과 교체
                swap(arr, rt, key);
            } else { // 엇갈리지 않았다면 lt와 rt의 값 교체
                swap(arr, lt, rt);
            }
        }

        return rt;
    }

    // 정복
    public static void solution(int[] arr, int start, int end){
        if(start >= end)
            return;

        int key = partition(arr, start, end);
        solution(arr, start, key -1);
        solution(arr, key + 1, end);
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n];
        for(int i = 0; i < n; i++)
            arr[i] = sc.nextInt();

        solution(arr, 0, n-1);
        for(int x: arr)
            System.out.print(x+" ");
    }
}

 

내림차순

import java.util.Scanner;

public class quickSort_reverse {
    public static void swap(int[] arr, int p1, int p2){
        int tmp = arr[p1];
        arr[p1] = arr[p2];
        arr[p2] = tmp;
    }

    // 분할
    public static int partition(int[] arr, int start, int end){
        int key = start;
        int lt = start + 1;
        int rt = end;

        while(lt <= rt){ // 엇갈릴 때까지 반복
            while( lt <= end && arr[lt] >= arr[key] ){ // 키 값보다 작은 값을 만날 때 까지
                lt++;
            }

            while(arr[rt] <= arr[key] && rt > start){ // 키 값보다 큰 값을 만날 때 까지
                rt--;
            }

            if(lt > rt) { // 현재 엇갈린 상태이면 키 값과 교체
                swap(arr, rt, key);
            } else { // 엇갈리지 않았다면 lt와 rt의 값 교체
                swap(arr, lt, rt);
            }
        }

        return rt;
    }

    // 정복
    public static void solution(int[] arr, int start, int end){
        if(start >= end)
            return;

        int key = partition(arr, start, end);
        solution(arr, start, key -1);
        solution(arr, key + 1, end);
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n];
        for(int i = 0; i < n; i++)
            arr[i] = sc.nextInt();

        solution(arr, 0, n-1);
        for(int x: arr)
            System.out.print(x+" ");
    }
}

시간 복잡도

최악의 경우 O(n^2) : 이미 정렬된 경우 (분할 정복의 이점을 사용하지 못함), 피봇에 따라서 편향되게 분할할 수 있다.

평균의 경우 O(nlogn)

공간 복잡도

주어진 배열 안에서 교환을 통해 정렬을 수행하므로 O(n)이다.

장점

• 불필요한 데이터의 이동을 줄이고 먼 거리의 데이터를 교환할 뿐만 아니라, 한 번 결정된 피벗들이 추후 연산에서 제외되는 특성 때문에, 시간 복잡도가 O(nlog₂n)를 가지는 다른 정렬 알고리즘과 비교했을 때도 가장 빠르다.
• 다른 메모리 공간을 필요로 하지 않는다.

단점

• 불안정 정렬(Unstable Sort) 이다.
• 정렬된 배열에 대해서는 Quick Sort의 불균형 분할에 의해 오히려 수행시간이 더 많이 걸린다.

 

---

source

https://gyoogle.dev/blog/algorithm/Quick%20Sort.html

퀵 정렬(Quick Sort) | 👨🏻‍💻 Tech Interview

https://blog.naver.com/ndb796/221226813382

5. 퀵 정렬(Quick Sort)

https://gyoogle.dev/blog/algorithm/Quick%20Sort.html