해나의 컴공생존기

1. Merge Algorithm sorting된 두개의 배열을 앞에서부터 각각 하나씩 비교하며 한 배열에 순서대로 합치는 알고리즘. 이 알고리즘의 단점은 하나의 배열을 새로 만들어야한다는 것이다 2. Recursive Merge Sort 위 코드를 간단히 설명해보자면 먼저 a[]와 똑같은 b[]를 만든다. h는 배열 전체 길이의 절반이다. b[0]부터 b[h-1] 까지 sort하는 함수를 한번 호출하고 b[h]부터 b[n-h-1]까지 sort하는 함수 하나를 호출한다. 끝까지 한 다음에는 마지막에 a로 sorting되며 합쳐진다. 증명 (proof by Invariant) invariant : 조건1 . a 배열이 입력이라고 가정하고 b배열이 sorting된 후 배열이라고 하면, a와 b의 값이 같아야..

우선 Merge Sort에 대해 알아 보기 전에 Merge에 대해 알아보자. Merge 와 Merge Sort 는 서로 같은 뜻 같지만 실제로는 둘이 조금 다르다. Merge 알고리즘은 soring 된 배열 두개를 합쳐서 새로운 배열을 만드는 알고리즘이다. 두 배열을 앞에서부터 비교해 나가면서 작은것들을 복사해서 한 배열에 넣는 알고리즘이다. 이러한 알고리즘을 이용하는 것이 Merge Sort 이다. 어떤 배열을 나눈다음에 서로 2그룹씩 합치면서 점점 올라오면서 정렬하는 것이 Merge Sort의 기본적인 로직이다. int sort(int a[], int n) { int h; int b[n]; h = n / 2; // copy a[] to b[] sort(b,h); // 반 나눈거의 앞부분 sort(b+..