[Java] 1517번. 버블 소트 (#병합 정렬)

1. 문항출처 : https://www.acmicpc.net/problem/1517

2. 문제해석

문제는 해당 숫자배열을 버블 정렬로 정렬할 때 몇번의 Swap이 일어나는지 묻는 문제인데,
직접 버블 정렬을 구현하고 Swap이 일어날 때마다 Count를 하게되면 시간초과가 난다.
따라서 시간복잡도가 N^2 인 버블 정렬이 아닌 NlogN인 병합정렬을 이용하여 풀어야만 한다.
'버블 소트'라는 제목부터 낚시질을 하는 기묘한 문제이다.


병합정렬은 기본적으로 분할과정과 병합과정으로 나뉘는데
병합과정에서 정렬이 일어날 때, 앞으로 이동하는 숫자가 있다면 그 숫자의 이동 칸수를 더해주면 된다.

3. 병합정렬

평균 시간복잡도가 NlogN인 퀵 정렬과 비교하여 장단점을 살펴보자면,
퀵 정렬의 경우에는 시간복잡도의 편차가 존재하여 최선의 경우 N이지만 최악의 경우 N^2이 발생할 수도 있다.
하지만 추가적인 메모리 사용이 필요없는 제자리정렬이라는 장점이 있다.
참고로 자바에서 java.util.Arrays에서 제공하는 sort 메서드는 퀵정렬이다.

반면, 병합정렬은 안정정렬이다.
어떤 경우에도 항상 안정적인 NlogN의 시간복잡도를 보장한다.
하지만 정렬하고자 하는 배열의 크기만큼의 메모리 공간을 추가로 요구하므로 대용량배열을 정렬할 경우에는 메모리 사용량에 유의하여야한다.

기본적인 병합정렬의 수행로직은 다음과 같다.
1. 재귀적 호출을 통해 각 배열을 잘게 쪼개나간다. (시간복잡도 logN)
2. 더이상 쪼갤 수 없게되면 각 쪼개진 그룹을 정렬하면서 병합한다(시간복잡도 N)

4. 해결코드

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

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static int N;
    static int[] array, temp;
    static long swapCount = 0;

    public static void main(String[] args) throws IOException {
        N = Integer.parseInt(br.readLine());
        array = new int[N];
        temp = new int[N];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) array[i] = Integer.parseInt(st.nextToken());
        mergeSort(0, N - 1);
        System.out.println(swapCount);
    }
	
    //병합정렬
    static void mergeSort(int start, int end) {
        if (start < end) {
            int middle = start + (end - start) / 2;
            mergeSort(start, middle);
            mergeSort(middle + 1, end);

            int left = start;
            int right = middle + 1;
            int index = start;
            while (left <= middle || right <= end) {
                if (right > end || (left <= middle && array[left] < array[right])) {
                    temp[index++] = array[left++];
                } else {
                	//병합과정에서 배열요소가 왼쪽으로 이동하게되면 이동칸수만큼 count
                    if(array[right] != array[index]) swapCount += right - index;
                    temp[index++] = array[right++];
                }
            }
            for (int i = start; i <= end; i++) array[i] = temp[i];
        }
    }

}