병합 정렬 (Merge Sort) 을 구현해보자

정렬을 할 수 있는 방법은 여러가지가 있다.

 

대표적으로 다음과 같은 방법이 있다.

 

💡 정렬의 종류와 방식

1. 버블 정렬 : 2개의 원소를 계속 비교해나가며 값이 큰 원소가 앞에 있는 경우 위치를 교환한다. 제일 큰 값(오름차순의 경우)을 제일 뒤로 보내어 최종적으로 정렬된다. 시간 복잡도는 O(N^2)으로 볼 수 있다. 만약 한번 순회했을 때 두 원소간 위치가 변한 적이 없다면 순회를 빠져나가는 방식으로 최적화를 할 수 있다.

2. 선택 정렬 : 원소들을 순회하여 가장 작은 값을 찾은 뒤(선택), 제일 앞 원소와 위치를 바꿈으로서 작은 값이 계속 앞으로 이동하면서 최종적으로 정렬된다. 시간 복잡도는 O(N^2)으로 볼 수 있다.

3. 삽입 정렬 : 2번째 원소부터 시작해서 N번째 원소까지 N-1까지의 정렬된 배열에 정렬을 유지할 수 있는 위치를 찾아 삽입하는 정렬이다. 시간 복잡도는 O(N^2)이고, 이미 어느정도 정렬되어있을때 효율적으로 동작할 수 있다.

 

위 방식은 최대 시간 복잡도가 O(N^2)이 된다.

 

하지만, 병렬 정렬을 사용하면 O(NlogN) 시간 복잡도로 정렬을 수행할 수 있다.

 

총 원소가 N개인 배열을 반복적으로 분할하여 최대한 작게 쪼갠다음에, 인접한 원소들끼리 비교하여 정렬하는 방식이다.

 

쪼개진 조각들을 합칠 때, 정렬해서 합침으로서 최종적으로 정렬된다.

 

구현

 

1. 분할 작업

2. 분할된 원소들을 정렬하여 합치는 작업

 

위 두가지 작업으로 분리해서 생각하면 쉽다.

 

분할 작업

	 private static void mergeSort(int[] arr, int left, int right) {
        if (right - left <= 1) {
            return;
        }

        int mid = (left + right) / 2;
        mergeSort(arr, left, mid);
        mergeSort(arr, mid, right);
        merge(arr, left, mid, right);
    }

 

분할할 수 없을 때까지 분할하고 merge 메서드를 호출한다.

 

merge 메서드는 분할된 두 배열을 정렬하여 합치는 메서드이다.

 

병합 작업

    private static void merge(int[] arr, int left, int mid, int right) {
        int[] temp = new int[right - left];
        int idx = 0, l = left, r = mid;

        while (l < mid && r < right) {
            if (arr[l] < arr[r]) {
                temp[idx++] = arr[l++];
            } else {
                temp[idx++] = arr[r++];
            }
        }

        while (l < mid) {
            temp[idx++] = arr[l++];
        }

        while (r < right) {
            temp[idx++] = arr[r++];
        }

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

임시 배열을 초기화하고, 첫번째 조건문으로 두 배열의 원소 크기에 따라 임시 배열에 입력하고

 

미처 입력되지 못한 원소들까지 순서대로 입력해준다.

 

그리고, 실제 배열 arr에 반영시켜주면 된다.

 

결과 확인

import java.util.Arrays;
import java.util.Random;

public class MergeSort {
    public static void main(String[] args) {
        int[] arr = new int[30];
        Random rand = new Random();
        for (int i = 0; i < 30; i++) {
            arr[i] = rand.nextInt(100);
        }

        System.out.println(Arrays.toString(arr));

        mergeSort(arr, 0, arr.length);

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

    private static void mergeSort(int[] arr, int left, int right) {
        if (right - left <= 1) {
            return;
        }

        int mid = (left + right) / 2;
        mergeSort(arr, left, mid);
        mergeSort(arr, mid, right);
        merge(arr, left, mid, right);
    }

    private static void merge(int[] arr, int left, int mid, int right) {
        int[] temp = new int[right - left];
        int idx = 0, l = left, r = mid;

        while (l < mid && r < right) {
            if (arr[l] < arr[r]) {
                temp[idx++] = arr[l++];
            } else {
                temp[idx++] = arr[r++];
            }
        }

        while (l < mid) {
            temp[idx++] = arr[l++];
        }

        while (r < right) {
            temp[idx++] = arr[r++];
        }

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

}

위 코드를 실행해보니 아래와 같이 잘 정렬됨을 확인할 수 있었다.

 

간혹, O(NlogN) 시간복잡도로 정렬을 수행할 필요가 있을 때 사용할 수 있도록 꼭 기억하고 있어야겠다.