알고리즘 (정렬) - 고급 정렬 알고리즘(Merge Sort)1

고급 정렬 알고리즘

선택정렬, 버블정렬, 삽입정렬 과 같은 기본 알고리즘은 모두 평균 ϴ(n²)의 시간이 소요된다. 하지만 앞으로 게시물에서 다룰 고급 정렬 알고리즘은  모두 평균 ϴ(n log n)의 시간이 소요된다. 병합 정렬, 퀵 정렬, 힙 정렬을 소개하는데  회악의 경우에도 병합 정령과 힙정렬은 ϴ(nlogn)이 소요되고, 퀵 정렬 ϴ(n²)이 소요된다. 이 중 퀵 정렬은 최악의 경우 때문에 성능이 가장 나빠 보일 수도 있으나 평균 성능은 어떤 정렬에도 뒤 떠러지지 않아 실무에서 가장 많이 사용된다.

 

병합 정렬(Merge Sort)

병합 정렬은 먼저 입력을 반으로 나눈다. 이렇게 나눈 전반부와 후반부를 각각 독립적으로 정렬한다. 마지막으로 정렬된 두 부분을 합쳐서, 즉 병합하여 정렬된 배열을 얻는다. 여기서 전반부를 정렬할 때도 역시 반으로 나눈다음 정렬해서 병합한다. 즉, 원래 정렬 문제와 성격이 똑같고 단지 크기만 반으로 줄었을 뿐이다. 후반부에 대한 정렬도 마찬가지다. 병합정렬은 자신에 비해 크기가 반인 문제를 두개 푼 다음, 이들을 병합하는 일을 재귀 적으로 반복한다.

 

public int [] mergeSort(int [] A, int p, int r){
    MergeSort ms = new MergeSort();

    //①
    int q = (int)Math.floor((p+r)/2);

    if((r-p) == 1) {
        int min = Math.min(A[p],A[r]);
        int max = Math.max(A[p],A[r]);
        A[p] = min;
        A[r] = max;
        return A;
    }
    if(r==p) return A;


    //②
    A = ms.mergeSort(A,p,q);
    //③
    A = ms.mergeSort(A,q+1,r);
    //④
    A = ms.merge(A,p,q,r);

    return A;
}

private int [] merge(int [] A, int p, int q, int r){
    int i = p; int j = q+1; int t = 0;

    int [] temp = new int[(r-p)+1];

    //⑥
    while (i <= q && j <= r){
        if(A[i] <= A[j]) {
            temp[t] = A[i];
            i++;
        }else{
            temp[t] = A[j];
            j++;
        }
        t++;
    }

    //왼쪽 부분 배열이 남은 경우
    while(i <= q){
        temp[t] = A[i];
        t++;
        i++;
    }

    //오른쪽 부분 배열이 남은 경우
    while (j <= r){
        temp[t] = A[j];
        t++;
        j++;
    }

   i = p; t = 0;
   while (i <= r){
       A[i] = temp[t];
       t++;
       i++;
   }

    return A;
}

 

 

mergeSort메서드

public int [] mergeSort(int [] A, int p, int r){
    MergeSort ms = new MergeSort();

    //①
    int q = (int)Math.floor((p+r)/2);

    //②
    if((r-p) == 1) {
        int min = Math.min(A[p],A[r]);
        int max = Math.max(A[p],A[r]);
        A[p] = min;
        A[r] = max;
        return A;
    }
    if(r==p) return A;


    //③
	A = ms.mergeSort(A,p,q);
    //④
    A = ms.mergeSort(A,q+1,r);
    //⑤
    A = ms.merge(A,p,q,r);

    return A;
}

👆최초 mergeSort() 호출시 파라미터
A[ ] = [5, 4, 7, 1, 2, 6, 3]
p = 0
r =  6

 

1️⃣ 주어진 배열 A의 가운데 index를 구한다. 배열의 요소가 7개 일 경우 p는 0 r은 6이된다. 이 때 (0+6)/2를 하면 index의 가운데인 index3을 구할 수 있다. 반면 배열의 요소가 8개 일 경우 p는 0 r은 7이 된다 이때 (0+7)/2를 하면 나머지가 발생 하므로 이 숫자를 무조건 내림해야 A를 배열의 가운데 index를 구할 수 있으므로 Math.floor() 함수를 사용한다. 

2️⃣는 재귀함수의 한계 조건 이므로 우선 첫번째 mergeSort를 호출했을 때는 넘어 간다. 더불어 if문의 조건인 r-p의 값도 0과 동일하지 않다. 3️⃣에서는 자기자신을 재귀호출 하고 있다. 이때 파라미더로 주어 지는 수는 위 그림에서 요소가 7개인 경우 에서도 오른쪽의 경우의 배열에 대한 정보로 재귀 호출된다.

 

 

각각 반으로 쪼개진 배열은 2️⃣한계조건에 if에 조건에 

 

 

merge 메서드

private int [] merge(int [] A, int p, int q, int r){
    int i = p; int j = q+1; int t = 0;

    int [] temp = new int[(r-p)+1];

    while (i <= q && j <= r){
        if(A[i] <= A[j]) {
            temp[t] = A[i];
            i++;
        }else{
            temp[t] = A[j];
            j++;
        }
        t++;
    }

    //왼쪽 부분 배열이 남은 경우
    while(i <= q){
        temp[t] = A[i];
        t++;
        i++;
    }

    //오른쪽 부분 배열이 남은 경우
    while (j <= r){
        temp[t] = A[j];
        t++;
        j++;
    }

   i = p; t = 0;
   while (i <= r){
       A[i] = temp[t];
       t++;
       i++;
   }

    return A;
}

 

merger()를 좀 더 구체적으로 기술하면 다음과 같다. 병합 정렬의 본체 코드 보다 길지만 하는 일은 단순 하다. 이미 정렬되어 있는 두 부분 배열 A[p ··· q]와 A[q+1 ··· r ]을 합쳐서 A[p···r]을 정렬된 상태로 만든다.

merge(A[],p,q,r)
// ▷A[p···q]와 A[q+1···r]을 병합하여 A[p···r]을 정렬된 상태로 만든다.
// ▷A[p···q]와 A[q+1···r]은 이미 정렬되어 있다.

 

 

 

[출처 - 쉽게 배우는 알고리즘(개정판),  저 문병로]
https://www.hanbit.co.kr/store/books/look.php?p_code=B7707942187

IT CookBook, 쉽게 배우는 알고리즘(개정판)