[Java]Merge sort

divide and conquer 방식으로 정렬!

 

divide and conquer
문제를 나눌 수 있을 때까지 나누고 , 서브 문제들을 동일하게 재귀적인 방식으로 해결한다.
만약 더이상 나눌 수 없다면 직접 해결한다

 

 

 

😎병합정렬 원리

예를 들어서 다음과 같은 배열이 있다고 가정하면 

이 배열을 계속해서 반으로 나눌 수 있다.

 

 

그리곤 각각의 sub 부분들을 비교해서 정렬한다

원소가 하나인 경우는 그 자체로 정렬되어 있으므로 원소 2개의 비교부터 시작한다.

 

[50,100] 배열과 [32,67] 배열을 비교해서 정렬해보자

먼저 각 배열의 첫번째 원소끼리 비교한다. 더 작은 수를 원 배열의 첫번째 인덱스에 넣고 다음 수로 넘어가 비교한다.

 

1. 50과 32 비교 -> 32가 더 작음 -> 배열에 첫번째 인덱스에 32 넣음 -> 32 다음 숫자인 67과 비교해줌

2. 50과 67 비교 -> 50이 더 작음 -> 배열의 두번째 인덱스에 50 넣음 -> 50 다음 숫자인 100과 비교해줌

3. 100과 67 비교 -> 67이 더 작음 -> 배열의 세번째 인덱스에 67 넣음 

4. 마지막 남은 원소인 100을 네번째 인덱스에 넣음

 

배열의 뒷부분도 정렬했다고 가정하면 이제 재귀를 빠져나오며 큰 부분도 정렬해준다.

이를 반복하여 전체를 정렬하는 것이 병합 정렬이다.

 

 

 

이를 코드로 구현해보자

😃병합정렬 코드

import java.util.Arrays;
    //Merge Sort 시간복잡도 O(nlogn)
    static void mergeSort(int[] arr, int start_idx, int end_idx){
        if(start_idx<end_idx){
            int middle = (start_idx+end_idx)/2;

            mergeSort(arr,start_idx,middle);
            mergeSort(arr,middle+1,end_idx);

            //분할 후 병합
            merge(arr,start_idx,middle,end_idx);
        }
        System.out.println("merged arr : " + Arrays.toString(arr));
       ;
    }
    //이 메서드가 실행할 일 : 시작 인덱스와 중간 인덱스를 받아 두 배열을 앞에서부터 비교하여 정렬해서 합쳐줌
    static void merge(int[] arr, int start_idx,int middle, int end_idx){
        int l = start_idx; //첫번째 배열 비교인덱스
        int r = middle+1; //두번째 배열 비교인덱스
        int idx = start_idx; //sorted 에 넣어줄 인덱스

        int[] sorted = new int[arr.length]; //정렬된 수를 넣어줄 배열
        //더 작은 수를 차례로 넣어줌
        while (l<=middle && r<= end_idx){
            if (arr[l] < arr[r]) sorted[idx++] = arr[l++];
            else sorted[idx++] =arr[r++];
        }
        //남은거 처리
        while (l<=middle) sorted[idx++] = arr[l++];
        while (r<=end_idx) sorted[idx] = arr[r++];

        //원래 배열에 정렬된 배열 넣어줌
        while (--idx>=start_idx){
            arr[idx] = sorted[idx];
        }
    }
}

다음 코드를 크기 8인 배열을 넣어서 정렬해보자!

public class Sort {
    public static void main(String[] args){
        int[] arr= {8,2,4,5,1,7,3,6}; //임의의 배열 생성
        mergeSort(arr,0,7);

    }

출력값

정렬이 잘 된 것을 볼 수 있다.

 

 

⏱️시간 복잡도

코드에 의하면 merge sort는 2n번의 swap과정과 logn번의 비교과정이 들어감

실행 시간은 nlogn으로 비교적 짧다.

하지만 배열의 크기가 커지면 커질 수록 비례해서 성능이 나빠지는 특성이 있기 때문에

mergeSort 보다 quick sort가 더 자주 사용된다.

 

 

 

https://develoyummer.tistory.com/76

[java]Quick Sort