[Algoritm] 초보자도 쉽게이해하는 병합정렬 알고리즘! 백준문제풀이, java

병합정렬(Merge Sort)

 

 

 

병합정렬 개념, 병합정렬이란?

 

병합정렬은 안정정렬에 속하며 분할 정복 알고리즘 중 하나이다. (분할정복은 문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음 결과를 모아서 원래의 문제를 해결하는 전략으로 순환 호출을 이용하여 구현한다)

 

하나의 문제를 두 개의 균등한 크기로 분할하고 분할된 작은문제들을 정렬한다. 그렇게 정렬된 부분리스트를 최종적으로 병합하여 전체가 정렬된 리스트가 되게하는 방법이다. 각 문제는 크기가 1이 될때까지 재분할하여 정렬을 시도한다. 

 

보통 재귀함수로 구현된다.

 

 

그림으로 이해하기

출처 : https://gmlwjd9405.github.io/2018/05/08/algorithm-merge-sort.html

 

출처 : https://gmlwjd9405.github.io/2018/05/08/algorithm-merge-sort.html

 

 

 

시간 복잡도

참고 https://rosweet-ai.tistory.com/52

최고/최악

• O(nlog₂n)

 

 

장단점 (사용하면 좋은/나쁜 상황)

장점

• 안정 정렬방법으로, 데이터의 분포에 영향을 덜받는다. 즉 입력데이터가 무엇이든 정렬 시간은 동일하다. 
• 만약 레코드를 연결리스트(Linked List)로 구성하면 링크 인덱스만 변경되므로 데이터의 이동은 무시할수 있을정도로 작아진다. 
  • 제자리 정렬로 구현할 수 있다.
• 크기가 큰 레코드를 정렬할 경우 연결리스트를 사용하면, 퀵정렬을 포함한 다른 어떤 정렬방법보다 효율적이다.

단점

• 배열로 구성할 경우, 제자리정렬(in-place sorting)이 아니기 때문에 추가적인 공간이 필요하다. 
• 원소의 크기가 큰 경우에 이동횟수가 많아져 매우 큰 시간적 낭비를 초래한다.

 

 

소스코드 예시와 설명 (백준 2751문제, 1517_ java)

백준 2751 문제 병합정렬로 풀기

  문제 -  https://www.acmicpc.net/problem/2751

import java.io.*;

public class 병합정렬_2751 {
    public static int[] A, tmp;
    public static long result;

    public static void main(String[] args)throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int N = Integer.parseInt(br.readLine());
        A = new int[N+1];
        tmp = new int[N+1];
        for(int i=1; i<=N; i++){
            A[i] = Integer.parseInt(br.readLine());
        }
        mergetSort(1,N);
        for(int i=1;i<=N;i++){
            bw.write(A[i]+"\n");
        }
        bw.flush();
        bw.close();
    }
    public static void mergetSort(int s, int e){
        if(e-s<1) return;
        int m = s+(e-s)/2;
        mergetSort(s,m);
        mergetSort(m+1,e);
        for(int i=s; i<=e; i++){
            tmp[i] = A[i];
        }
        int k=s;
        int index1=s;
        int index2=m+1;
        while(index1 <=m && index2<=e){
            if(tmp[index1]>tmp[index2]){
                A[k]=tmp[index2];
                k++;
                index2++;
            } else {
                A[k]=tmp[index1];
                k++;
                index1++;
            }
        }
        while(index1<=m){
            A[k] = tmp[index1];
            k++;
            index1++;
        }
        while(index2<=e){
            A[k]=tmp[index2];
            k++;
            index2++;
        }
    }
}

 

백준 1517 문제 병합정렬로 풀기

  문제 -  https://www.acmicpc.net/problem/1517

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

public class 병합정렬_버블소트프로그램_1517 {
    public static int[] A, tmp;
    public static long result;

    public static void main(String[] args)throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int N = Integer.parseInt(br.readLine());
        A = new int[N+1];
        tmp = new int[N+1];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i=1;i<=N;i++){
            A[i] = Integer.parseInt(st.nextToken());
        }
        result = 0;
        mergetSort(1,N);
        bw.write(result+" ");
        bw.flush();
        bw.close();
    }
    public static void mergetSort(int s, int e){
        if(e-s<1)return;
        int m = s+(e-s)/2;

        mergetSort(s,m);
        mergetSort(m+1, e);
        for(int i=s;i<=e;i++){
            tmp[i]=A[i];
        }
        int k=s;
        int index1=s;
        int index2=m+1;
        while(index1<=m&& index2 <=e){
            if(tmp[index1]>tmp[index2]){
                A[k] = tmp[index2];
                result = result+index2-k;
                k++;
                index2++;
            }else{
                A[k] = tmp[index1];
                k++;
                index1++;
            }
        }
        while(index1<=m){
            A[k]=tmp[index1];
            k++;
            index1++;
        }
        while(index2 <= e){
            A[k]=tmp[index2];
            k++;
            index2++;
        }
    }
}