[Unity C#] 합병 정렬

개념

 Merge sort는 분할정복법을 사용하여 정렬하는 알고리즘이다.

  1) 분할: 해결하고자 하는 문제를 작은 크기의 동일한 문제들로 분할

  2) 정복: 각각의 작은 문제를 순환적으로 해결

  3) 합병: 작은 문제의 해를 합하여(merge) 원래 문제에 대한 해를 구함

출처: https://excelsior-cjh.tistory.com/47 [EXCELSIOR]

과정

장점

퀵 정렬과 비슷하게 원본 배열을 절반씩 분할해가면서 정렬하는 정렬법으로써 분할하는 과정에서 logNlogN 만큼의 시간이 소요된다. 즉, 최종적으로 보게되면 N×logNN×logN이 된다. 또한 퀵 정렬과 달리 기준값을 설정하는 과정없이 무조건 절반으로 분할하기에 기준값에 따라 성능이 달라지는 경우가 없다. 따라서 항상 O(N×logN)O(N×logN)이라는 시간복잡도를 가지게 된다.

 

Stable Sort이다.

 

단점

병합정렬은 임시배열에 기존 배열에 계속해서 옮겨주며 정렬을 하는 방식이기에 추가적인 메모리가 필요하다는 점이다. 데이터가 최악인 면을 고려하면 퀵 정렬보다는 병합정렬이 훨씬 빠르기 때문에 병합정렬을 사용하는 것이 많지만, 추가적인 메모리를 할당할 수 없다면 병합정렬을 사용할 수 없기 때문에 퀵을 사용해야 하는 것이다.

 

시간복잡도

1/2한 Array에 대해 정렬하는데 걸리는 시간 T(n/2), 나머지 반의 Array에 대해 정렬하는데 걸리는 시간 T(n/2) 그리고 Merge하는데 필요한 횟수는 최대 n이다.

$$O(nlogn)$$

출처: https://excelsior-cjh.tistory.com/47 [EXCELSIOR]

소스코드

using System.Collections;
using System.Collections.Generic;
using System;
using UnityEngine;

public class MergeSort_Source : MonoBehaviour
{
    // Start is called before the first frame update
    void Start()
    {
        int[] arr = new int[7] { 38,27,43,3,9,82,10 };
        mergeSort(arr, 0, arr.Length-1); 

        for(int i = 0; i < arr.Length; i++){
            Debug.Log(arr[i]);
        }

    }

    void mergeSort(int[] arr, int left, int right){
        if(left < right){
            for (int i = 0; i < arr.Length; i++) {
                Debug.Log(arr[i]);
            }
            int mid = (left + right) / 2;
            //Left부터 다 돌고
            //Left에 포함된 Right다 돌고
            //Right 다 돌기

            //left 0 right 6 - 왼 38 27 43 3|9 82 10 
            //left 0 right 3 - 왼 38 27|43 3|9 82 10 
            //left 0 right 1 - 왼 38|27|43 3|9 82 10 
            mergeSort(arr, left, mid); // 왼쪽에서 계속 분할
            //1. left 0 mid 3 - 38 27 43 3|9 82 10 왼
            //2. left 0 mid 1 - 38 27|43 3|9 82 10 왼 
            //3. left 0 mid 0 - (38) 27|43 3|9 82 10종료

            //6. mid 2 right 3 - (27 38)|(43)3|9 82 10 오
            mergeSort(arr, mid + 1, right);// 오른쪽에서 계속 분할
            //4. mid 1 right 1 - 38 (27)|43 3|9 82 10종료 왼
            //7. mid 2 right 3 - (27 38)|43 (3)|9 82 10 오
            merge(arr, left, mid, right);
            //5. left 0 right 1 - (27 38)|43 3|9 82 10 왼
            //8. mid 2 right 3 - (27 38)|(3 43)|9 82 10 오
            //9. 왼 오 다 들렸으니까 merge차례 (3 27 38 43) | 9 82 10

        }

    }


    void merge(int[] arr, int left, int mid, int right)
    {
        Debug.Log("left : " + left + " mid : " + mid + " right : " + right);
        int[] L = copyofRange(arr, left, mid);// 8번 27 38
        int[] R = copyofRange(arr, mid + 1, right);// 8번 3 43

        // 3 27 38 43 | 9 10 82
        int leftindex = 0, rightindex = 0, k = left;
        int leftlen = L.Length, rightlen = R.Length;
               // 0 1 2 3      0 1 2
        while (leftindex < leftlen && rightindex < rightlen)
        {
            if (L[leftindex] <= R[rightindex]) // 왼쪽이 작거나 같으면
            {
                arr[k++] = L[leftindex++];

            }
            else
            {
                arr[k++] = R[rightindex++];
            }
        }
        //38 27에서 k == 0, rightindex == 0 ,leftindex == 0으로
        //arr[0] = R[0]이 되어
        //27 27 43 3 9 82 10로 데이터 변경

        while (leftindex < leftlen)
        {
            arr[k++] = L[leftindex++];
        }
        while (rightindex < rightlen)
        {
            arr[k++] = R[rightindex++];
        }

        //따라서 k++ j++되어 k == 1, j == 1, i == 0이 되고 
        //arr[1] = L[0]이 되어 
        //27 38 43 3 9 82 10로 정상적으로 바뀜
        //즉 Switching을 해주기 위해서 나머지 값을 다음 인덱스에 할당함

    }

    int[] copyofRange(int[] arr, int start, int right){
        int len = right - start + 1; // 원래는 +1이 없는, L R 초기화 가독성을 위해 추가해줌 
        int[] copyarr = new int[len];

        Array.Copy(arr,start,copyarr,0,len); // arr의 start부터 복사를 시작하여 copyarr의 0부터 len까지 저장한다
        return copyarr;
    }

}