[정렬] 병합정렬

정렬

정렬 알고리즘	정의	시간복잡도
삽입	대상을 선택해 정렬된 영역에서 선택 데이터의 적절한 위치를 찾아 삽입하면서 정렬하는 방식	O(N) ~ O(N^2)
버블	데이터의 인접 요소끼리 비교하고, swap 연산을 수행하며 정렬하는 방식	O(N^2)
선택	대상에서 가장 크거나 작은 데이터를 찾아가 선택을 반복하면서 정렬하는 방식	O(N^2)
퀵	pivot 값을 선정해 해당 값을 기준으로 정렬하는 방식	O(NlogN) ~ O(N^2)
힙	이진트리를 이용하여 최대힙(오름차순)/최소힙(내림차순) 트리를 구성해 정렬하는 방식	O(NlogN)
병합	이미 정렬된 부분 집합들을 효율적으로 병합해 전체를 정렬하는 방식	O(NlogN) + 추가적인 메모리 필요
기수	데이터의 자릿수를 바탕으로 비교해 데이터를 정렬하는 방식	O(N) + 추가적인 메모리 필요

 

병합정렬

병합정렬은 분할 정복 방식을 사용해 데이터를 분할하고 분할한 집합을 정렬하며 합치는 알고리즘
시간복잡도의 평균값은 O(NlogN) 이다

코딩테스트에의 정렬관련 문제에서 자주 등장 ( 특히 2개의 그룹을 병하는 원리는 꼭 숙지해야함 )

 

 

병합정렬 핵심 이론

순서	배열
첫번째	42 (set1)	32 (set2)	24 (set3)	60 (set4)	15 (set5)	5 (set6)	90 (set7)	45 (set8)
두번째	32 (set1)	42 (set1)	24 (set2)	60 (set2)	5 (set3)	15 (set3)	45 (set4)	90 (set4)
세번째	24( set1)	32 (set1)	42 (set1)	60 (set1)	5 (set2)	15 (set2)	45 (set2)	90 (set2)
네번째 (정렬)	5	15	24	32	42	45	60	90

• set를 작은 단위의 그룹으로 나눈다
• 2개의 그룹씩 병합하며 정렬을 진행한다

 

2개의 그룹 정렬하는 방법

투포인터를 사용하여, 정렬 진행

24 (set1)	32 (set1)	42 (set1)	60 (set1)	5 (set2)	15 (set2)	45 (set2)	90 (set2)
(set1 인덱스)	-> 이동			(set2 인덱스)	-> 이동
(인덱스를 이동하면서, 더 작은 값을 먼저 배열에 저장)
5	15	24	32	42	45	60	90

• index를 서로 움직이면서, 더 작은 값을 먼저 배열에 저장하는 구조 ( 투포인터를 이용한 정렬 )

 

병합 정렬 구현

• 과정)
  • 첫번째 while문에서 왼쪽 혹은 오른쪽 그룹의 index 끝까지 도달하게 됨
  • 나머지 while문에서 남은 수 들을 arr에 넣어주는 역할
• megerSort()
  • startIndex ~ middleIndex / middleIndex + 1 ~ endIndex (2개의 그룹) 
  • arr : 메서드 종료 전에 2개의 그룹이 합쳐져서 정렬이 됨
  • tmp : 2개의 그룹을 합치기 전의 배열 저장

public class App {
    public static void main(String[] args) throws Exception {
        int[] arr = {2,4,1,3,5,6};
        mergeSort(arr, 0, arr.length - 1);
        printArray(arr);
    }

    private static void mergeSort(int[] arr, int startIndex, int endIndex){
        if (endIndex - startIndex < 1){
            return;
        }
        int middleIndex =startIndex+ (endIndex -startIndex)/2;
        mergeSort(arr, startIndex, middleIndex);
        mergeSort(arr, middleIndex + 1, endIndex);

        int[] tmp = new int[arr.length];
        for(int i =startIndex; i<= endIndex; i++){
            tmp[i] = arr[i];
        }

        int index1 = startIndex;
        int index2 = middleIndex+1;
        int sortIndex = startIndex;
        while(index1 <= middleIndex && index2 <= endIndex){
            if( tmp[index1] > tmp[index2] ){
                arr[sortIndex] = tmp[index2];
                index2++;
                sortIndex++;
            }else{
                arr[sortIndex] = tmp[index1];
                index1++;
                sortIndex++;
            }
        }

        while(index1 <= middleIndex){
            arr[sortIndex] = tmp[index1];
            sortIndex++;
            index1++;
        }

        while(index2 <= endIndex){
            arr[sortIndex] = tmp[index2];
            sortIndex++;
            index2++;
        }
    }


    private static void printArray(int[] arr){
        for (int i : arr) {
            System.out.println(i);
        }
    }
}