[G1] 버블 소트2 : Java : 1517 - 합병 정렬

문제

1517번: 버블 소트

 

 

 

 

 

접근 방법

 버블 정렬의 이동은 한 번에 한칸씩만 이동할 수 있다. swap의 횟수를 찾기 위해서는 부분 리스트가 1개가 될 때까지 쪼개고 점점 합병해가면서 합치는 합병 정렬이 알맞다고 생각했지만 합병 정렬은 가까운 요소끼리 먼저 정렬을 하기 때문에 기준 요소와 모두 비교를 진행하고 swap하는 버블 정렬과는 다른 결과가 나올 것이라 생각했다.

 

 책을 보며 풀이법을 봤지만 사실 아직도 이해가 안간다. 버블 정렬은 현재 위치가 정렬이 완료된 정답 위치라도 비교하는 과정에서 앞, 뒤로 위치가 계속 바뀌어서 비효율적인 알고리즘이라고 알고 있는데 합병 정렬에서의 merge과정과 버블 정렬의 swap을 같은 단계라고 생각을 하면 버블 정렬은 정답 위치가 되는 순간 자리가 바뀌지 않아야지만 같은 단계라고 볼 수 있지 않나 생각이 든다. 

 

책의 풀이를 빌리자면 '두 그룹을 병합하는 과정에 버블 정렬의 swap이 포함되어 있다는 것을 알 수 있다.'라고 적혀있는데 병합 과정이 어떻게 버블 정렬의 swap이랑 같은 횟수로 진행된다는 것을 보장할 수 있는지를 모르곘다. 풀이법을 정리하자면

1. mege가 일어날 때 j번째 요소가 i번째 요소보다 작으면 이동을 하면서 swap이 일어난다
2. 이때 바뀐 인덱스 차이를 모두 더하면 총 일어나는 swap의 위치를 알 수 있다. 

 

 모르겠는 것은 버블 정렬은 기준점을 계속 바꿔가면 모든 요소를 비교해서 가장 오른쪽 리스트에 정렬된 데이터가 1개씩 쌓이는 것이고, 합병 정렬은 리스트를 계속 2개로 쪼개면서 1개가 남을 때까지 쪼개다가 점점 합병해가면서 정렬을 하는데 왜 풀이가 이렇게 되는지를 모르겠다!! 내 머릿속으로는 버블 정렬은 하나하나 다 비교해서 쓸데없는 swap이 나올것 같고 합병 정렬은 이미 정렬이 완료된 블록 단위처럼 움직이니깐 블록과 블록이 만나서 비교하는 것도 다를 것 같은 생각이다... 

 

 

 

코드 - Java

import java.io.*;
import java.util.StringTokenizer;


public class Main {
    public static long sorted [];
    public static long swapCount = 0;
    public static void main(String[] args) throws IOException {

        // 1.입력 받기
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        long A [] = new long [N+1];

        StringTokenizer st = new StringTokenizer( br.readLine());
        for(int i=0; i< N; i++){
            A[i] = (Integer.parseInt(st.nextToken()));
        }

        // 2. 합병 정렬
        sorted = new long[N*2];
        merge_sort(A, 0, N-1);

        System.out.println(swapCount);
    }
    

    public static void merge(long list[], int left, int mid, int right){

        int i,j,k,l;
        i =left; j = mid+1; k = left;
        /* 분할 정복된 list의 합병 */
        while (i <= mid && j <= right){
            if(list [i] <= list[j]){
                sorted[k++] = list[i++];

            }else{
                swapCount += j - k;
                sorted[k++] = list[j++];

            }
        }
        if(i>mid){
            for(l=j ; l <= right; l++){
                sorted[k++] = list[l++];
            }
        }
        else{
            for(l=i ; l <= right; l++){
                sorted[k++] = list[l++];
            }
        }

        // swap 횟수 구하기
       // comparePos(sorted, left, right);

        /* 배열 sorted[]의 리스트를 배열 list[]로 복사 */
        for(l=left; l<= right; l++){
            list[l] = sorted[l];

        }
    }

    public static void merge_sort(long list [], int left, int right){
        int mid;
        if(left < right){
            mid = (left + right)/2;
            merge_sort(list, left, mid);
            merge_sort(list, mid+1, right);
            merge(list, left, mid, right);
        }
    }



}