합병정렬

17 Jan 2021 in Algorithms

알고리즘 설명

IDEA : 두 개의 정렬된 배열이 주어졌을 때, 정렬된 하나의 배열로 합병. 이걸 divide-and-conquer 방법으로.

1. 배열 원소가 하나가 될 때 까지 배열을 반으로 쪼개고 쪼개고 쪼갠다.
2. 거기서 부터 정렬시작!
3. 함수(배열, 시작점, 끝점) 로 recursive하게

성능 분석

일단 합병정렬 말고, 정렬된 두개 배열을 합칠 때 성능을 보면 다음과 같다.

• 주요 함수는 comparison 과 movement
• comparis2on의 횟수, n1+n2
• comparison 은 n1+n2 보다 작거나 같다.

합병정렬 성능

• 재귀트리를 이용해 나타내면 더 이해하기 쉽다.
• Θ(nlogn)

과정

아래 과정을 반복한다. 트리의 전위순회.

JAVA 코드

• 푸는 방법이 여러개다. 나는 좀 안 깔끔하게 풀긴 했다. 세련된 코드를 외우도록 해보자.

• 일단 이중 for문을 사용했고, 그 for 문을 다 돌면 ary가 정렬이 되는게 아니라서 좀 지저분하게 조건을 추가했다.

  1. 첫번째 배열 : 첫번째 for 문으로 순회 (start 에서 mid)
  2. 두번째 배열 : 두번째 for 문은 (mid에서 end)
  • 여기서 헷갈리지말아야하는게, 첫번째 두번째 배열은 사실 한 배열이고, index로 두개처럼 우리가 임의로 생각하는 것이다.

• 경우의 수는 다음과 같다.

  1. 첫번째 배열(ary,start,mid)은 새 배열(n_ary)에 정렬이 되었는데, 두번째 배열(ary,mid,end)은 아직 안됨
     • 이 경우, 이중for문 밖에 나온 상태라다. 이중 for문 안에서 두번째 배열이 어디까지 진행됐는지 알기 위해 check라는 변수를 사용해 확인하고, 또 for문을 돌려 end전까지 두번째 배열 원소들을 n_ary에 순서대로 차곡차곡 넣어준다.
  2. 두번째 배열(ary,mid,end)이 새 배열(n_ary) 다 정렬되었는데 , 첫번째 배열(ary,start,mid)은 아직 안됨.
     • 이 경우는 두번째 for문은 다 돈 상태다. 그러므로 첫번째 for문은 끝나지 않았다. ptr이라는 변수로 확인해주고 n_ary가 어디까지 차있는지 확인하고 첫번째 배열 원소들을 n_ary에 순서대로 차곡차곡 넣어준다.

static int[] ary = {11,120,89,3,5,2,122,13,22,123,1222};
static int[] n_ary = new int[ary.length];

public static void main(String[] args) {
    merge_sort(ary,0,ary.length);
    System.out.println("결과들 : " +Arrays.toString(n_ary) );
}

public static void merge_sort(int[] ary,int start,int end){
    int mid =(end+start)/2;

    if(start>=end-1){
        return;
    }else{
        merge_sort(ary,start,mid);
        merge_sort(ary,mid,end);
    }

    int ptr=start;
    int check = mid;

    for(int i =start;i<mid;i++) {
        for(int j=check;j<end;j++){
            if(ary[i]>ary[j]){
                n_ary[ptr]=ary[j];
                check = j+1;
            }else{
                n_ary[ptr]=ary[i];
                j=end+1;
            }
            ptr++;
        }
        if(ptr <end) {
            if(check>=end) {
                n_ary[ptr]=ary[i];
                ptr++;}
        }
    }
    for(int j=check;j<end;j++) {
        n_ary[ptr] = ary[j];
        ptr++;
    }

    for(int i =start ; i<end;i++) {
        ary[i] = n_ary[i];
    }	
}

• 함수 두개로 나눠서 divide 기능하는 거랑 merge하는 거랑.

public static void main(String[] args){
    int[] ary = {3,2,23,12,45,27,11,662,5,1,4};
    int[] result = merge_sort(ary,0,ary.length);
    for (int i =0;i<ary.length;i++) {
        System.out.print(result[i]+" ");
    }

}

private static int[] merge_sort(int[] ary,int start, int end) {
    int mid = (start+end)/2;
    if(start+1==end) {
        int[] ele= {ary[start]};
        return ele;
    }
    int[] left = merge_sort(ary,start,mid);
    int[] right = merge_sort(ary,mid,end);
    int[] temp = merge(left,right);
    return temp;
}

private static int[] merge(int[] left, int[] right) {
    int l = left.length;
    int r = right.length;
    int[] temp = new int[l+r];
    int i=0;
    int j=0;
    int cnt=0;

    while (i<l && j<r) {
        if(left[i]<=right[j]) {
            temp[cnt]=left[i];
            i++;
        }else{
            temp[cnt]=right[j]; 
            j++;
        }
        cnt++;
    }

    while (i<l){
        temp[cnt]=left[i];
        cnt++;i++;
    }
    while (j<r) {
        temp[cnt]=right[j];
        cnt++;j++;
    }
    for (int a =0;a<temp.length;a++) {
        System.out.print(temp[a]+ ",");
    }		
    System.out.println();
    return temp;
}

PYTHON 코드

• 푸는 방식이 여러가지다. 이번엔 while문으로 푼다. 이게 훨씬 깔끔하고, array 다룰때 java보다 python이 훨씬 편하구나.

ary= [13,24,1,2,734,23,12,5]
print(merge_sort(ary))
def merge_sort(ary):
    #원소가 한개면 나눌게 없으니까 이때부터 ary가 정렬 시작이 된다. 그 전에는 계속 쪼갬
    if len(ary) <= 1:
        return ary
    #java에서는 int(/2) 이렇게 하는걸 python에서는 //2 를 사용함
    mid = len(ary)//2
    #python 에서는 아래처럼 쉽게 배열을 나눌 수 있다. 좋다.
    leftAry = merge_sort(ary[:mid])
    rightAry = merge_sort(ary[mid:])
    return merge(leftAry, rightAry)

def merge(left, right):
    #일단 원소 개수 할당할 필요가 없어서 편하다. 
    #배열 원소?를 index 마음대로 뺐다 넣었다 할 수 있어 편하다..
    result = []
    while len(left)>0 or len(right)>0 :
        if len(left)>0 and len(right)>0:
            if(left>right):
                result.append(right[0])
                #이렇게 하면 index 생각할 필요 없이 앞에 요소 줄어든다.!
                right= right[1:]
            else :
                result.append(left[0])
                left=left[1:]
        elif len(left)>0 :
            result.append(left[0])
            left=left[1:]
        elif len(right)>0:
            result.append(right[0])
            right= right[1:]            
    return result