처음

이번에는 몇 종류의 정렬 알고리즘을 공부했다. 어차피 후술할 알고리즘들을 섞고 발전시킨 정렬 함수가 Arrays나 Collections 클래스에 모두 있지만, 적어도 기본적인 정렬 방법들에는 무엇이 있는지 정도는 알아둬야할 것 같다. 그냥 새로운 종류의 알고리즘을 접하고 짜보는 것만으로도 공부가 되기도 하니까 말이다.

중간

1. Merge Sort

가장 먼저 알아볼 것은 병합 정렬 (Merge Sort)다. 이름이 병합 정렬인 이유는 대상 배열을 재귀적으로 쪼개고, 병합하는 과정이 수반되기 때문이었다. 병합 정렬의 메인 아이디어는 길이가 각각 N, M인 두 개의 정렬된 배열을 합쳐 정렬하는 데는 O(N+M)의 시간복잡도가 필요하다는 것이다. (각 배열에 pointer로 비교해가며 합치기)

그럼 기존의 배열을 쪼개서 뭔가를 하겠다는 것은 알겠는데, 쪼갠 두 개의 배열들은 어떻게 정렬할까? 그것은 배열을 재귀적으로 계속 쪼갠 후에, 합치는 것이다. base condition은 배열의 길이가 1이 될 때가 될 것이고, 길이가 1인 배열은 이미 정렬된 상태이다.

package sort;

import java.util.Arrays;

public class Merge {
    static int[] test;
    public static void main(String[] args) {

        test = new int[]{-1, 1, 5, -3, -15, 15, 35, 12,13,17,0};
        mergeSort(0, test.length);

        System.out.println(Arrays.toString(test));
    }

    //en-st==2 일 때 st~mid, mid~en이 각각 하나씩 언소를 가진당

    //st~mid, mid~en이 각각 정렬되어있을 때 증렬~
    private static void merge(int st, int en) {
        int mid = (st + en) / 2;
        int pf = 0;
        int pb = 0;

        int[] front = Arrays.copyOfRange(test, st, mid);
        int[] back = Arrays.copyOfRange(test, mid, en);

        for (int i = 0; i < en - st; i++) {
            if (pf >= front.length) test[st + pf + pb] = back[pb++];
            else if (pb >= back.length) test[st + pf + pb] = front[pf++];
            else if (front[pf] <= back[pb]) test[st + pf + pb] = front[pf++];
            else test[st + pf + pb] = back[pb++];
        }
    }

    private static void mergeSort(int st, int en) {
        if (en - st == 1) return;
        int mid = (st + en) / 2;

        mergeSort(st, mid);
        mergeSort(mid, en);
        merge(st, en);
    }
}

merge()는 두 개의 배열을 합치는 함수다. st와 en가 test라는 배열에 합칠 두 배열들의 인덱스다. mergeSort는 merge sort를 실제로 실행하는 함수다.

merge sort의 특징

우선 merge sort의 시간복잡도는 O(nlogn)다. 우선 배열을 쪼개는 과정에서는 함수가 각 단계별로 1, 2, 4, ... N번 호출되고, 이것은 O(n)이다. 또 쪼개진 배열을 대소 비교하며 병합할 때는, 각 단계마다 n번의 원소 검사가 일어날 것이고, 이 단계는 n = 2^k로 표현했을 때, k번 반복된다. 따라서 nk = nlogn의 시간복잡도를 갖는다.

또한 merge sort의 중요한 특징 중 하나는 stable sort라는 점이다. stable sort는 값이 같은 원소가 있을 때, 기존의 순서를 유지하는 정렬을 말한다. merge() 함수에서 앞쪽 배열과 뒷쪽 배열을 비교할 때, 앞 배열의 요소가 작거나 같은 경우에 집어넣는다. 두 원소가 같을 때는 앞쪽에 있는 것을 먼저 집어넣는다는 말이다.

자바의 Collections.sort()는 merge sort와 insert sort를 합친 tim sort를 활용하기 때문에, stable한 정렬이 가능하다.

2. Quick Sort

두 번째는 퀵 소트 (Quick Sort)다. quick sort는 pivot 원소를 정해, 이것을 기준으로 왼편에는 pivot보다 작은 원소를, 오른편엔 큰 원소를 위치하게 하는 과정을 반복함으로써 정렬한다. pivot으로 배열을 두 부분으로 나누고, 나누어진 배열에서도 각각 pivot을 만들어 pivot을 기준으로 나눈다. 이 과정이 반복된다. 역시 재귀함수를 이용한다.

package sort;

public class Quick {
    private static void sort(int[] arr, int r, int l) {
        if (r >= l) return;

        int mid = partition(arr, r, l);
        sort(arr, r, mid - 1);
        sort(arr, mid, l);
    }

    private static int partition(int[] arr, int r, int l) {
        int p = arr[(r + l) / 2];
        while (r <= l) {
            while (arr[r] < p) r++;
            while (arr[l] > p) l--;
            if (r <= l) {
                swap(arr, r, l);
                r++;
                l--;
            }
        }
        return r;
    }

    private static void swap(int[] arr, int x, int y) {
        int tmp = arr[x];
        arr[x] = arr[y];
        arr[y] = tmp;
    }
}

sort 함수가 정렬을 실행하는 함수이고, partition()은 해당하는 구간의 배열을 pivot을 기준으로 재배치하는 함수다. merge sort와 비슷한 형태기 때문에 이해하기 어렵진 않았다.

quick sort의 특징

quick sort의 시간복잡도도 약 O(nlogn)이다. 모든 단계에서 모든 원소를 확인하는 과정이 필요하므로 각 단계별로 n번의 탐색이 발생하고, 배열이 두 덩이로 쪼개지면 평균적으로 logn번의 단계가 필요하므로, O(nlogn)인 것이다. 하지만 배열이 정렬된 형태인 경우에는, 최대 O(n^2)의 시간복잡도를 갖는다. 매 단계에서 pivot의 위치가 맨 앞 또는 맨 뒤에 위치하기 때문에, 단계가 n번 반복되기 때문이다.

자바의 Arrays.sort()는 두 개의 pivot을 활용하는 dual pivot quick sort를 활용한다. unstable하고, 최대 시간복잡도가 O(n^2)라는 점에 주의하자.

끝

가장 대표적인 O(nlogn) 정렬인 quick sort와 merge sort에 대해서 알아봤다. 그 밖에 counting sort나 radix sort 등은 특별한 경우이므로 구현 없이 개념만을 이해했다. 다음 포스팅에서는 배열과 관련된 연습 문제를 몇 개 풀어볼 예정이다.

출처 : 바킹독 블로그