[알고리즘] 병합 정렬(MergeSort) 핵심 아이디어

책 [Do it! 알고리즘 코딩 테스트 - 자바 편;김종관 지음]을 참고하여 작성하였습니다. 

 

• 분할 정복(divide and conquer) 방식: 데이터를 분할하고 분할한 집합을 정렬하며 합치는 알고리즘
• 가장 작은 데이터 집합(크기 1)으로 나눈 후 2개의 그룹을 합치면서 정렬
• 2개의 그룹을 합칠 때는 투 포인터를 이용하여 둘 중 더 작은 수를 결과 배열에 먼저 저장
• 그런 다음 포인터를 1씩 증가시키는데, 어느 한 포인터가 배열의 끝에 먼저 도달하면 나머지 배열의 값들도 옮겨 붙임   
• 시간 복잡도는 평균 O(nlogN)
  - 크게 보면 row 하나 당 n번의 데이터 접근
  - 병합 과정에서 logN번만큼 정렬

https://en.wikipedia.org/wiki/Merge_sort

버블 정렬(swap)과 연관지은 핵심 아이디어

- 버블 정렬에서는 swap이 몇 번 일어날까

https://www.youtube.com/watch?v=KNKj8QSbRXE&t=816s

- 첫째 줄에서 5는 가장 작은 수이므로 0번째로 이동한다 -> 이때 앞에 있는 요소들 4개 역전

- 두 번째 줄에서는 15가 1번째로 이동한다 -> 이때 앞에 있는 요소들 4개 역전

- 세 번째 줄에서는 24가 2번째로 이동한다 -> 역전할 게 없으니 0개 

- 네 번째 줄에서는 32가 3번째로 이동한다 -> 역전할 게 없으니 0개

- 다섯 번째 줄에서는 42가 4번째로 이동한다 -> 역전할 게 없으니 0개

- 여섯 번째 줄에서는 45가 5번째로 이동한다 -> 이때 앞에 있는 요소 1개 역전

- 일곱 번째 줄에서는 60이 6번째로 이동한다 -> 역전할 게 없으니 0개

- 마지막으로 90이 마지막 인덱스로 이동한다 -> 역전할 게 없으니 0개

 

그렇기 때문에 총 4+4+1=9번의 swap이 일어난다

 

- 그런데 병합 정렬에서는 투 포인터를 사용하여 swap의 과정을 최소화

 

https://www.acmicpc.net/problem/1377

https://www.acmicpc.net/problem/1517 ***

[https://github.com/doitcodingtest/java/blob/main/%EC%A0%95%EB%A0%AC/P1517_%EB%B2%84%EB%B8%94%EC%86%8C%ED%8A%B82.java] 코드는 여기 참고

java/정렬/P1517_버블소트2.java at main · doitcodingtest/java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static int[] arr;
    static int[] tmp;
    static long count = 0L;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        arr = new int[n + 1];
        tmp = new int[n + 1];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        merge_sort(1, n);
        System.out.println(count);
    }

    private static void merge_sort(int st, int end) {
        // 병합 정렬
        if (end - st < 1) {
            return;
        }

        int mid = st + (end - st) / 2;
        merge_sort(st, mid);
        merge_sort(mid + 1, end);
        for (int i = st; i <= end; i++) {
            tmp[i] = arr[i];
        }
        int k = st; // 결과 배열의 인덱스
        int idx1 = st;
        int idx2 = mid + 1;
        while (idx1 <= mid && idx2 <= end) {
            if (tmp[idx2] < tmp[idx1]) { // swap
                arr[k] = tmp[idx2];
                count += (idx2 - k);
                k++; idx2++;
            } else {
                arr[k++] = tmp[idx1++];
            }
        }
        while (idx1 <= mid) {
            arr[k++] = tmp[idx1++];
        }

        while (idx2 <= mid) {
            arr[k++] = tmp[idx2++];
        }
    }
}

 

결과적으로 정렬 전의 인덱스와 정렬 후의 인덱스의 차가 swap 하는 데 드는 비용

chatGPT