해나의 컴공생존기

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의 값이 같아야..

1. sorting의 조건 정확하게 sorting이 되기 위해서는 아래의 두가지 조건이 성립되어야한다. 조건1 . a 배열이 입력이라고 가정하고 b배열이 sorting된 후 배열이라고 하면, a와 b의 값이 같아야한다. 조건2. 배열 b는 b[0]n−1 일 때 sort 함수가 성공한다고 가정하자. 항상 재귀 실행 전에 a[0]에 최소값이 들어간 후 실행된다. 따라서 재귀로 들어가기 전부터 ∀x((x>0)→(a[0]a[0]