[Algorithm] 여러 가지 정렬2 - 빠른 정렬(1)

[여러 가지 정렬 1]에 나오는 정렬들 보다는 조금 복잡하지만 더 빠른, 배열을 정렬(오름차순)하는 방법을 알아보자.

 

1. Merge Sort

• 배열을 분할하여 각각 정렬하고, 정렬된 결과를 합치는 분할정복(Divide and Qunquer) 방식
• 주어진 배열을 둘로 나누어 각각 정렬하고, 이를 하나로 합친다. -> 둘로 나뉜 부분 배열은 어떻게 정렬할까?
  • 둘로 나뉜 배열을 또 둘로 나누어 각각을 정렬하고, 이를 하나로 합친다. -> 또 나뉜 배열을 둘로 나누고, ...
  • 길이가 N인 배열을 정렬하기 위해서는 길이가 N/2인 배열을 정렬해야 하고, 또 그 배열을 정렬하기 위해서는 길이가 N/4인 배열을 정렬해야 하고, ... , 결국 길이가 1인 배열을 정렬해야 하는데, 길이가 1인 배열을 정렬하는 것은 너무나도 쉽다.

Merge Sort의 예시

• 이렇게 주어진 배열을 쉽게 해결할 수 있을 때까지 쪼개어서 sub problem을 해결하고, 이를 merge하는 전형적인 분할정복 기법이다. 
• 분할할 때 N의 시간, 합칠 때 N의 시간, 합칠 때의 level이 logN이므로 시간복잡도는 O(N*logN)이다.

import java.util.Arrays;

public class MergeSort {

    public static int[] arr = new int[]{6, 5, 12, 10, 9, 1};
    public static int[] temp;

    public static void mergeSort(int left, int right) {

        if (left < right) {
            int mid = (left + right) / 2;

            //배열을 절반으로 나누어 재귀를 실행한다.
            mergeSort(left, mid);
            mergeSort(mid + 1, right);

            //다 나누었다면 병합한다.
            merge(left, mid, right);
        }
    }

    public static void merge(int left, int mid, int right) {

        int l = left, r = mid + 1;
        int idx = left;

        //두 sub array의 인덱스를 다 돌면서 확인.
        while (l <= mid && r <= right) {
            //왼쪽 sub array와 오른쪽 sub array의 값을 비교하면서 더 작은 값을 순서대로 임시 배열에 넣는다.
            if (arr[l] <= arr[r]) {
                temp[idx] = arr[l];
                idx++;
                l++;
            } else {
                temp[idx] = arr[r];
                idx++;
                r++;
            }
        }

        if (l > mid) {
            //임시 배열에 왼쪽 sub array가 먼저 다 채워졌을 떄,
            //오른쪽 sub array의 data가 아직 남아있다면 나머지를 임시 배열에 채워준다.
            while (r <= right) {
                temp[idx] = arr[r];
                idx++;
                r++;
            }
        } else {
            //위와 반대의 경우
            while (l <= mid) {
                temp[idx] = arr[l];
                idx++;
                l++;
            }
        }

        for (int i = left; i <= right; i++) {
            arr[i] = temp[i];
        }

    }


    public static void main(String[] args) {

        temp = new int[arr.length];
        mergeSort(0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }

}

• 장점
  • 어떠한 경우에도 O(N*logN)의 성능을 보장한다.
  • 안정 정렬(Stable Sort)이다. (중복된 데이터가 있을 경우, 정렬 시 중복된 데이터의 원래 순서가 바뀌지 않음)
• 단점
  • 정렬된 데이터를 저장할 임시 배열이 추가로 필요하다.

 

2. Quick Sort

• 거의 모든 정렬보다 속도가 빨라 많은 라이브러리에서 정렬 알고리즘으로 쓰이고 있다.
• Merge Sort와 마찬가지로 분할 정복(Divide and Qunquer) 방식으로, 하나의 pivot을 골라 pivot보다 작은 값은 왼쪽에, 큰 값은 오른쪽에 위치시킨다.
  • 한 번의 pivot을 정하면 배열이 두 부분으로 나뉘는데, 나뉜 두 부분에 대해 각각의 pivot을 선정하여 위를 반복한다. (재귀)
  • 한 번의 재귀호출이 끝나게 되면, 적어도 하나의 데이터는 위치가 정해지게 된다.

Quick Sort 예시

• 만약 pivot을 기준으로 나뉜 배열을 임시 배열에 저장하고, 임시 배열의 결과를 기존 배열에 덮어쓰는 방식으로 구현한다면 쉽게 구현할 수 있겠지만, 이는 Merge Sort와 마찬가지로 추가적인 배열이 필요하게 된다.
• Quick Sort는 추가적인 공간이 필요없이, 기존 배열 안에서의 swap만으로 정렬을 해낼 수 있다.

import java.util.Arrays;

public class QuickSort {

    public static int[] arr = new int[]{19, 17, 15, 12, 16, 18, 4, 11, 13};

    public static void swap(int a, int b) {
        int tmp = arr[a];
        arr[a] = arr[b];
        arr[b] = tmp;
    }

    public static void quickSort(int start, int end) {

        if (start + 1 >= end) {
            return;
        }

        int pivot = arr[start]; //pivot의 선택에 따라 알고리즘의 성능이 달라질 수 있다. 여기서는 배열의 첫 번쨰로
        int l = start + 1;
        int r = end - 1;

        while (true) {
            //배열에서 pivot보다 큰 값이 나올 때까지 l을 이동시킨다.
            while (l <= r && arr[l] <= pivot) {
                l++;
            }
            //배열에서 pivot보다 작은 값이 나올 때까지 r을 이동시킨다.
            while (l <= r && arr[r] >= pivot) {
                r--;
            }

            //l이 r보다 커지게 되면 배열을 다 확인했다는 뜻
            if (l > r) {
                break;
            }
            
            //pivot보다 작은 값과 큰 값이 도출되어 둘의 자리를 바꾼다.
            swap(l, r);
        }

        //pivot보다 작은 값이므로 pivot과 자리를 바꿔준다.
        swap(start, r);
        
        //재귀
        quickSort(start, r);
        quickSort(r + 1, end);
    }

    public static void main(String[] args) {

        quickSort(0, arr.length);
        System.out.println(Arrays.toString(arr));
    }

}

• pivot의 위치를 어디로 정하냐에 따라 Quick Sort의 성능에 영향을 미칠 수 있다.
• 장점
  • 최선과 평균 시간복잡도는 O(NlogN)이다.
  • 한 번 자리가 결정된 pivot이 추후 연산에서 제외되는 특성 때문에, O(NlogN)을 가지는 다른 정렬 알고리즘과 비교했을 때 가장 빠르다.
  • 기존 배열 이외에 추가적인 오버헤드가 필요하지 않다. (l, n이 있긴 한데 굉장히 작아서...)
• 단점
  • 정렬이 많이 이루어진 배열에 대해 수행할 경우, 불균형 분할에 의해 최악의 경우 O(N^2)의 시간이 걸릴 수 있다.
  • Unstable 정렬이다.

 

3. Counting Sort

• 배열의 데이터가 나오는 횟수를 세서, 차례대로 출력한다.
• 굉장히 간단해보이지만 제약사항이 존재한다.
  • 각 수의 등장 횟수를 배열의 인덱스에 저장하기 때문에 데이터가 양수여야 한다. (배열의 크기를 수의 범위의 2배로 할 경우 음수도 가능하긴 함)
  • 수의 범위가 너무 크지 않아야 한다. (만약 수의 범위가 0에서 10억일 경우, 배열을 10억 1의 크기로 만들어야 함)

public class CountingSort {

    public static int[] arr = new int[]{2, 8, 6, 9, 13, 1, 2, 2};
    public static int[] freq = new int[14]; //수의 범위만큼 잡아야 함.

    public static void countingSort() {
        for (int i = 0; i < arr.length; i++) {
            freq[arr[i]]++;
        }
    }

    public static void main(String[] args) {

        countingSort();
        for (int i = 0; i < freq.length; i++) {
            while (freq[i]-- > 0) {
                System.out.print(i + " ");
            }
        }
    }

}

• O(N+K)의 시간복잡도를 가진다. (K: freq배열의 크기 = 수의 범위)
• 장점
  • 정렬하는 수의 범위가 특정될 때, 범위가 작을 때 유용하다.
  • K의 크기가 작다면 O(N)에 가까운 성능을 보인다.
• 단점
  • 배열의 최대값이 클수록 성능이 낮아진다.
  • 데이터의 크기의 간격이 크다면 메모리의 낭비가 심하다.