백준#2751 2023-10-27

https://www.youtube.com/watch?v=QAyl79dCO_k

참고한 영상

 

병합 정렬 소스..

using System;

using System.Text;

class HelloWorld {

  static void Main() {

      StringBuilder stringBuilder = new StringBuilder();

            int count = int.Parse(Console.ReadLine());

        int[] arr = new int[count];

       

        for(int i = 0; i < count; i++) {

            arr[i] = int.Parse(Console.ReadLine());

        }

       

     

        int[] tmp = new int[arr.Length];

        MergeSort(arr,tmp,0,arr.Length-1);

     

        for(int i = 0; i < arr.Length; i++)

        {

            stringBuilder.Append(arr[i] + "\n");

        }

        Console.Write(stringBuilder);

  }

 

      static void Merge(int[] arr,int[] tmp, int start, int mid, int end) {

        for(int i = start; i <= end; i++) {

            tmp[i] = arr[i];

        }  

        int pointStart = start;

        int pointMid = mid + 1;

        int index = start;

        while(pointStart <= mid && pointMid <= end) {

            if(tmp[pointStart] <= tmp[pointMid]) {

                arr[index] = tmp[pointStart];

                pointStart++;

            } else {

                arr[index] = tmp[pointMid];

                pointMid++;

            }

            index++;

        }

        for(int i = 0; i <= mid - pointStart; i++) {

            arr[index + i] = tmp[pointStart + i];

        }

    }

    static void MergeSort(int[] arr,int[] tmp, int start, int end) {

        if(start < end) {

            int mid = (start + end) / 2;

            MergeSort(arr,tmp,start,mid);

            MergeSort(arr,tmp,mid + 1, end);

            Merge(arr,tmp,start,mid,end);

        }

    }

}

디버깅 결과

Original Array:
6 8 7 1 5 9 4 3 2 10 
LEFT
6
RIGHT
8
Merge
6 8

LEFT
6 8
RIGHT
7
Merge
6 7 8

-------------------------------------
LEFT
1
RIGHT
5
Merge
1 5

LEFT
6 7 8
RIGHT
1 5
Merge
1 5 6 7 8

-------------------------------------
LEFT
9
RIGHT
4
Merge
4 9

LEFT
4 9
RIGHT
3
Merge
3 4 9

-------------------------------------
LEFT
2
RIGHT
10
Merge
2 10

LEFT
3 4 9
RIGHT
2 10
Merge
2 3 4 9 10

-------------------------------------
LEFT
1 5 6 7 8
RIGHT
2 3 4 9 10
Merge
1 2 3 4 5 6 7 8 9 10

-------------------------------------
Sorted Array:
1 2 3 4 5 6 7 8 9 10

 

이런식으로 합쳐지는건 이해했지만 결과적으론, 아직 50퍼밖에 이해 못한거같다.

또 다른 정렬 방식들을 접하면 조금씩 이해 될듯.... 알고리즘은 어렵당..