[개념 학습 및 정리] 고급 정렬

1. 기본 정렬

• 선택 정렬
• 삽입 정렬
• 버블 정렬

 

모두 시간 복잡도는 O(n^2)이다.

 

 

 

2. 고급 정렬

시간 복잡도를 O(n logn)으로 정렬하는 방법은 다음과 같다.

• 합병 정렬
• 퀵 정렬
• 힙 정렬

 

합병과 퀵 정렬은 재귀호출 혹은 재귀적인 구조를 이용한 정렬이다.

---

로그는 지수함수의 역함수이다. 컴퓨터 공학에서 log를 사용하는 경우 그 밑이 2이므로 보통 밑을 생략한다.

로그와 지수

 

 

 

3. 합병 정렬

1) 합병 정렬이란 ?

매번 배열을 절반으로 나누고 각각 정렬한 뒤 합치는 방법이다. T(n)은 n개의 숫자를 합병정렬 할 때의 시간 복잡도로 O(n logn)과 동일하다. 

합병 정렬

2) 시간 복잡도

T(n)은 n개의 숫자를 합병 정렬로 정렬하는데 걸리는 시간이다.

• 왼쪽 합병 정렬은 T(n/2)의 시간복잡도
• 오른쪽 합병 정렬은 T(n/2)의 시간복잡도
• 합칠 때는 O(n)의 시간복잡도
• T(n) = 2 x T(n/2) + O(n) = 점화식

시간 복잡도

시간 복잡도에 대한 계산은

...

... (K 번째)

마지막 K 번째에서 T(1)이 되도록 한다면 n이 k+1이 되어야하고 즉, k+1 = log n이라는 뜻이다. 따라서 최종적으로는 다음과 같은 수식이 된다.

 

결국 몇번이나 절반으로 나눌 수 있어야 하나가 나오는지, 즉 2를 몇번을 곱해야 n이 나오는지이다.

3) 합병 정렬 재귀 디자인

• void mergeSort(int[] arr, int s, int e)은 s번째 값부터 e번째 값까지 정렬하는 함수
• if(s >= e) return;은 원소가 하나만 있을 때 동작 확인 

 

import java.io.*;
import java.util.StringTokenizer;

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

        mergeSort(arr, 0, arr.length-1);
        for(int i = 0; i < n; i++) bw.write(arr[i] + " ");

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

    static void mergeSort(int[] arr, int s, int e) {
        if(s >= e) return;

        int mid = (s+e)/2;
        mergeSort(arr, s, mid);
        mergeSort(arr, mid+1, e);
        merging(arr, s, mid, mid+1, e);
    }

    static void merging(int[] arr, int s1, int e1, int s2, int e2) {
        int p = s1;
        int q = s2;
        int[] temp = new int[arr.length];
        int temp_idx = 0;

        while(p <= e1 && q <= e2) {
            if(arr[p] <= arr[q]) {
                temp[temp_idx++] = arr[p++];
            } else {
                temp[temp_idx++] = arr[q++];
            }
        }

        if(p > e1) {
            for(int i = q; i <= e2; i++) {
                temp[temp_idx++] = arr[i];
            }
        } else {
            for(int i = p; i <= e1; i++) {
                temp[temp_idx++] = arr[i];
            }
        }

        for(int i = s1; i <= e2; i++) {
            arr[i] = temp[i-s1];
        }
    }
}

 

 

 

4. 퀵 정렬

1) 퀵 정렬이란 ?

원소를 하나 정하여(pivot) 해당 원소보다 같거나 작은 수들과 큰 수들로 나누는 방법이다.

• pivot의 위치는 정렬을 해도 변하지 않는다.
• pivot의 왼쪽과 오른쪽의 자리가 바뀌지 않는다. 즉, 따로 정렬해도 된다.

 

 

퀵 정렬

2) 시간 복잡도

T(n)은 n개의 숫자를 퀵 정렬로 정렬하는데 걸리는 시간이다.

• pivot 정하기는 O(1)의 시간 복잡도
• 작거나 같은 값과 큰 값을 분류는 모든 원소를 비교하기 때문에 O(n)의 시간 복잡도
• 각각을 퀵 정렬
• T(n) = T(left) + T(right) + O(n)

 

퀵 정렬은 pivot에 따라 왼쪽과 오른쪽이 달라지기 때문에 정확한 계산은 못한다. 따라서 pivot이 원소의 개수를 절반으로 나눈다고 가정하여 계산을 하면 된다. 그렇다면 수식은 합병 정렬 수식과 동일해진다. 결국, 퀵 정렬도 평균적으로 O(n logn)의 시간복잡도를 가지게 된다.

• T(n) = 2T(n/2) + O(n)

 

단, 최악의 경우(원소가 다 정렬되어있을 때 혹은 역순으로 정렬되어있을 때)에는 O(n^2)이 걸린다. pivot에 따라서 시간복잡도가 정해지기 때문에 맨 첫번째, 끝, 랜덤, 앞의 세게의 숫자에서 중간값을 구하는 등 여러가지 전략을 통해 할 수 있지만 근본적으로 최악의 경우를 피할 수 없다. 따라서 O(n logn)만큼의 시간 복잡도를 가지기 위해서는 전체 숫자들 중에서 O(n)만으로 중간 값을 구해야한다.

3) 퀵 정렬 재귀 디자인

• void quickSort(int[] arr, int s, int e)은 s번째 값부터 e번째 값까지 정렬하는 함수
• if(s >= e) return;은 원소가 하나만 있을 때 동작 확인 

 

import java.io.*;
import java.util.StringTokenizer;

public class Main {

    static int[] left;
    static int[] right;

    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());

        StringTokenizer st = new StringTokenizer(br.readLine());
        int[] arr = new int[n];
        for(int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        left = new int[n];
        right = new int[n];

        quickSort(arr, 0, n-1);
        for(int i = 0; i < n; i++) bw.write(arr[i] + " ");
        bw.newLine();

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

    static void quickSort(int[] arr, int s, int e) {

        if(s >= e) return;

        // 가장 첫 번째 요소를 pivot으로 설정
        int pivot = arr[s];
        int left_cnt = getLeft(arr, s+1, e, pivot);
        int right_cnt = getRight(arr, s+1, e, pivot);

        for(int i = 0; i < left_cnt; i++) {
            arr[s+i] = left[i];
        }
        arr[s+left_cnt] = pivot;
        for(int i = 0; i < right_cnt; i++) {
            arr[s+left_cnt+1+i] = right[i];
        }
        quickSort(arr, s, s+left_cnt-1);
        quickSort(arr, s+left_cnt+1, e);
    }

    static int getLeft(int[] arr, int s, int e, int pivot) {
        int idx = 0;
        for(int i = s; i <= e; i++) {
            if(arr[i] <= pivot) left[idx++] = arr[i];
        }
        return idx;
    }

    static int getRight(int[] arr, int s, int e, int pivot) {
        int idx = 0;
        for(int i = s; i <= e; i++) {
            if(arr[i] > pivot) right[idx++] = arr[i];
        }
        return idx;
    }
}